递归
什么是递归
递归是一种直接或间接调用自身函数或方法的函数或者方法。
递归的优缺点
优点
递归的优点是逻辑简单清晰,对于一些问题用递归解决非常方便。
缺点
递归的缺点是调试困难,递归层次过多时,容易造成栈溢出。
递归的组成
递归的组成包括递归头和递归体两部分。
递归头
上面说到递归是直接或间接调用自身函数或方法的函数或方法,也就是说没有条件限制,递归算法就会无限循环直到崩溃,
因此想要完成一个完整的递归算法,递归头是不可或缺的。
递归体
递归体的作用是不断缩小问题的规模,知道逼近递归结束的条件也就是递归头
代码示例
说到递归,那肯定是递归的经典题:斐波那契数列:斐波那契数列的递归写法如下:
#include<iostream>
using namespace std;
int Fibonacci(int n) {
if (n == 1||n==2) {
return 1;
}
else
{
return Fibonacci(n-2) + Fibonacci(n - 1);
}
}
int main() {
int n = 0;
cin >> n;
cout<<Fibonacci(n);
}
如上面代码所示,递归头是n1||n2,也就是当n等于1或者2时,递归结束,返回1;
递归体为Fibonacci(n-2) + Fibonacci(n - 1),也就是当n不等于1或者2时,继续递归调用Fibonacci函数,直到n等于1或者2。
下面是递归的流程图
在上面的流程图中我们会发现:当n=5时,进入递归,会把f(5)分成发f(4)和f(3)而f(4)和f(3)还会继续分解,最后触碰到f(2)或f(1)
所以可以看成一大堆f(2)和f(1)相加