👨‍🎓作者简介：一位喜欢写作，计科专业的大二菜鸟

🏡个人主页：starry陆离

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

📚订阅专栏：『算法笔记HNUCM-OJ』如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦

『递归概念与典型实例』

1.引言

1-100求和

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

伪代码：

fori=1to100

  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.递归的定义

在调用一个函数的过程中又出现直接或间接调用该函数本身，称为函数的递 归(Recursion)调用，这种函数称为递归函数

• 若p函数定义中调用p函数，称之为直接递归
  
• 若p函数定义中调用q函数，而q函数定义中又调用p函数，称之为间接递归
  

3.递归的要素

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

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

intsum(intn){

    if(n==1)return1;//递归结束条件

    elsesum(n-1)+n;//递归表达式

}

4.递归特点

(1) 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的 求解方法与原问题完全相同，只是在数量规模上不同

(2) 递归调用的次数必须是有限的

(3) 必须有结束递归的条件来终止递归

5.递归的使用条件

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

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

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

6.递归的优缺点

递归的优缺点

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

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空 间都比非递归算法要多

解决方法：在某些递归算法中可消除递归调用，使其转化为非递归算法

7.典型递归实例

7.1求阶乘

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

intf(intn){

    if(n==1)return1;//递归结束条件

    elsen*f(n-1);//递归表达式

}

7.2Fibonacci数列

斐波那契(Fibonacci)数列因数学家列奥纳多·斐波那 契以兔子繁殖为例引入，故又称为“兔子数列”。

intfibonacci(intn){

    if(n<=1)return1;//递归结束条件

   returnfibonacci(n-1)+fibonacci(n-2);//递归表达式

}

7.3青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。

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

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