-
Notifications
You must be signed in to change notification settings - Fork 22
递归和迭代
L edited this page Jan 15, 2020
·
1 revision
递归,就是在运行的过程中调用自己。
构成递归需具备的条件:
- 子问题须与原始问题为同样的事,且更为简单;
- 不能无限制地调用本身,须有个出口,化简为非递归状况处理。
迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程
以斐波那契数列的求解为例
斐波那契数列为:0,1,1,2,3,5...
递归的实现
int fib(int n)
{
if(n>1)
return fib(n-1) + fib(n-2);
else
return n; // n = 0, 1时给出recursion终止条件
}
迭代的实现
int fib(int n){
int i, temp0, temp1, temp2;
if(n<=1)
return n;
temp1 = 0;
temp2 = 1;
for(i = 2; i <= n; i++){
temp0 = temp1 + temp2;
temp2 = temp1;
temp1 = temp0;
}
return temp0;
}
递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换.
能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出.