递归与非递归
发布网友
发布时间：2022-05-04 21:24
我来回答
共2个回答
热心网友
时间：2022-06-26 00:29
首先要理解递归本身其实是一项非常重要的算法技巧。
递归满足两个条件：
1，不断调用函数本身，也就是递归函数。
2，调用是有限的，也就是递归出口。
为了理解方便，下面是用一个最简单的例子：求N的阶乘。
n!(阶乘)定义：
n!数学意思为n! = n*(n-1)! & 1!=1;
其实根据上面递归定义结合分析下就可以n阶乘的递归算法：
1,构造一个递归函数,不断乘以自身和使用自身减一后调用同样函数．
2,定义出口，当函数参数等于1时结束;
如果用ISO C++语言描述如下：
int Factorial(int n){
if( n > 1){
return n*Factorial(n-1);//递归函数调用
}
else if(n == 1){
return 1; //递归出口
}
else{
return ERROR;//报告输入错误
}
}
这里讨论主要的不是上面这个简单的例子，而是下面的一些改良．
因为递归设计大量的堆栈操作，所以一般都会考虑将递归转为非递归来执行．
这里用上面这个程序作一个分析例子来分析．
假设这里执行Factorial(4)，那么程序会按照下面方式来执行：
(1)执行Factorial(4)判断n > 1执行Factorial(3),并且将Factorial(4)函数相关信息存入一个堆栈．
(2)执行Factorial(3)判断n > 1执行Factorial(2),并且将Factorial(3)函数相关信息存入一个堆栈．
(3)执行Factorial(2)判断n > 1执行Factorial(1),并且将Factorial(2)函数相关信息存入一个堆栈．
(4)执行Factorial(1)判断n == 1执行返回1;
(5)将Factorial(2)函数从堆栈中弹出，执行2*1，并且返回2．
(6)将Factorial(3)函数从堆栈中弹出，执行2*3，并且返回6．
(7)将Factorial(4)函数从堆栈中弹出，执行6*4，并且返回24．
如下图所示：
Factorial(4)
-->Factorial(3);
-->Factorial(2);
-->Factorail(1);
<--Factorail(1);
<--Factorial(2);
<--Factorial(3);
<--结果
可以看到中间涉及的堆栈操作是很大的开销，每次需要保存当前函数的所有信息．
为了避免这样情况，可以使用下面这几种方法来实现递归到非递归的转换．
(1) 循环方法
循环方法是所有递归到非递归的转换中最理想的方法，可以将开销减少到最小．
不过也是分析起来最复杂的，对于简单的递归可以用这样的方法来处理．
例如：Factorial计算
这里回到n!(阶乘)定义上面来分析，这里将n!数学意思为n! = n*(n-1)! & 1!=1;做一个扩展可以到到n!另外一个表示方法n! = n*(n-1)*(n-2)*....*1;
这样就可以很容易得到另外一个定义：
n!表示执行n次循环计算一个增量k，初始k=1和结果t=1;每次t乘以k++的值.
ISO C++实现代码如下：
Factorial(int n){
int k = 1 ;//增量
int t = 1 ;//临时结果
while(k!=n){
t*=k;
k++;
}
return t;
}
这样可以避免递归带来的大量堆栈操作．
(2) 自定义堆栈
对于复杂逻辑的堆栈操作，需要借助外部堆栈来实现．
因为对于所有的递归操作最后分析出来都是形成的一颗树形结构．
下面是一个递归实现Factorial的一个方法，虽然在这个程序中对比循环来相对复杂，不过对于一些不能分析出来循环的递归操作来说自定义堆栈的方法可以达到空间开销可控．
Factorial(int n){
Stack s;
int t = 1;//临时变量
s.push(n);
while(s.top()!=1)[
t *= s.top();
s.push(s.top()-1);
s.pop();
}
return t;
}
除了上面这两种方法外，还可以使用一种迭代的方法实现递归到非递归的处理．
热心网友
时间：2022-06-26 00:29
用栈或者迭代
