"Recursion" recursion concept and typical examples

​
​

活动地址：CSDN21天学习挑战赛

作者简介：一位喜欢写作,计科专业大二菜鸟

个人主页：starry陆离

首发日期：2022年8月2日星期二

上期文章：『算法导论』什么是算法？什么是程序？

订阅专栏：『算法分析与设计』
每日推荐：『牛客网-面试神器』

如果文章有帮到你的话记得点赞+收藏支持一下哦

---

---

1.引言

问题：1-100求和

方法1：使用循环求和 1+2+3+4+5+6+……+99+100

伪代码：
for i=1 to 100
   sum = sum + i

方法2：换个角度思考

sum(n)表示1…n的和 

sum(100) = sum(99) + 100  

= sum(98) + 99 + 100  

= ……  

= sum(1) + 2 + 3 + 4 + …… + 99 + 100  

= 1 + 2 + 3 + 4 +…… + 99 + 100

2.递归的定义

In the process of a function called againCall this function directly or indirectly by itself,Referred to as a function of parcels 归(Recursion)调用,这种函数称为递归函数

• 若pFunction definition callp函数,称之为直接递归

• 若pFunction definition callq函数,而qFunction definition and callp函数,称之为间接递归

3.递归的要素

1、递归表达式 （递归方程）

2、递归结束条件 （边界条件）

int sum(int n){
    
	if(n==1)return 1;//递归结束条件
	else sum(n-1)+n;//递归表达式
}

4.递归特点

(1) 需要解决的问题Can be converted into one or more child problems to solve,And these subproblems 求解方法The same with the original problem,只是在数量规模上不同

(2) The number of recursive calls must be有限的

(3) 必须End of recursion condition来终止递归

5.Scope of application of recursive

(1) 定义是递归的（阶乘、斐波那契数列等）

(2) 数据结构是递归的（单链表、二叉树等）

(3) 问题的求解方法是递归的（汉诺塔、回溯法等）

6.递归的优缺点

优点：结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便

缺点：递归算法的运行效率较低,Both cost calculation time and take up the storage of empty More than the non-recursive algorithm between

解决方法：In some of the recursive algorithm can eliminate the recursive call,使其Into non-recursive algorithm

7.Typical case of recursive

7.1求阶乘

n!=1×2×3×……×n

int f(int n){
    
	if(n==1)return 1;//递归结束条件
	else n*f(n-1);//递归表达式
}

7.2Fibonacci数列

斐波那契(Fibonacci)Sequence for mathematicians leonardo·斐波那 Qi in the rabbit breeding, for example to introduce,故又称为**“兔子数列”**.

int fibonacci(int n){
    
	if(n<=1)return 1;//递归结束条件
    return fibonacci(n-1)+fibonacci(n-2);//递归表达式
}

7.3青蛙跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级.

• 求该青蛙跳上一个n级的台阶总共有多少种跳法？

就是fibonacci的变形题,读者可自行实现

每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环,这里推荐一款算法面试神器：牛客网-面试神器;算法题只有多刷勤刷才能保持思路与手感,大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）

如果文章有帮到你的话记得点赞+收藏支持一下哦