什么样的递归不能改成非递归？

如果使用盏，
任何递归都可以化成非递归。
如果不用盏，
有的递归可以改成迭代。
我想知道的时候，
如果不借助于盏，
到底什么递归何时可以改成非递归，
何时不能？

36 个解决方案

#1

一个例子:
Ackerman函数就不能改为非递归

A(1,0)=2
A(0,m)=1 m>=0
A(n,0)=n+2, n>=2
A(n,m)=A(A(n-1,m),m-1) n,m>=1

#2

我还知道hanoi也不能改成非递归，
我想要此问题的描述、总结，或者说定理，
而不是个别例子。
3x

#3

hanoi也不能改成非递归 ？？
能给出证明么？

#4

2,已知Ackerman函数的定义如下:
n+1 m=0
akm(m,n) = akm(m-1,1) m0,n=0
akm(m-1,akm(m,n-1)) m0,n0
(1)写出递归算法
(2)写出非递归算法
递归算法:
int akm(int m, int n)
{
if (m == 0) akm = n+1 ;
else if( n == 0)
akm = akm(m-1 , 1);
else
6.4 递归的模拟
{
g=akm(m , n-1);
akm=akm(m-1 , g) ;
}
}//akm
非递归算法:
int akm1(int m , int n)
{/*S[MAX]为附设栈,top为栈顶指针*/
top = 0 ; S[top].mval = m ; S[top-1].nval=n ;
do {
while (S[top].mval){
while(S[top].nval){
top++ ; S[top].mval=S[top-1].mval; 
6.4 递归的模拟
S[top].nval=S[top-1].nval-1 ;
}
S[top].mval-- ; S[top].nval=1 ;
}
if (top>0)
{ top -- ;
S[top].mval -- ;
S[top].nval=S[top+1].nval+1;
}
}
while (top !=0 || S[top].mval != 0);
akm1=S[top].nval+1 ; top-- ;
}//akm1

#5

我认为学过数据结构的朋友都知道递归是用栈来实现的，
  那么，递归转化为非递归的程序都可以用栈来描述（当然如果用循环就可以解决的就不必了）
  
  so：所有的递归在理论上都可以转化成非递归的。 只不过在转化过程中的难易程度有不同。还有实现所消耗的空间和时间特别大~

#6

楼上的我可能没说清楚。
我再举个例子吧，比如说求阶乘，
f(n)=n*f(n-1)，
这个是递归，
但是这个很容易可以改成递推。
x=1;
for(int i=2;i<=n;i++)
  x*=i;
然后就求出结果了，
这就是我要的非递归，
而不是手动使用栈。
但是对于汉诺塔程序，
是不能改成递推的，
你不信可以试试。

我的意思就是说不要使用栈，
直接改成循环。

所以我的问题是，
什么情况下肯定可以把递归改成循环？

#7

for() 和数组 联合在一起，也可以实现栈的哦。。。呵呵！

#8

感觉lz把问题的面！搞的太窄了

#9

栈保存了全部数据，
循环只保存当前数据，
是吧？

#10

尾递归可以改成迭代，其他的递归都不行。所谓尾递归是指递归调用的语句在递归函数的最后一句，

#11

其实主要就是看这个算法需要的最小空间复杂度是多少.
如果空间复杂度可以降低到O(1),那么就没必要用递归了.
不然,用不用递归本质上没有区别

#12

hanoi是可以用非递归的

#13

guohuang(菜瓜头) ( ) 信誉：100  2006-7-19 10:10:24  得分: 0  
尾递归可以改成迭代，其他的递归都不行。所谓尾递归是指递归调用的语句在递归函数的最后一句，

#14

都可以非递归

对于计算机来说，递归就是一个循环而已

#15

guohuang(菜瓜头) ( ) 信誉：100  2006-7-19 10:10:24  得分: 0  
 
 
   
尾递归可以改成迭代，其他的递归都不行。所谓尾递归是指递归调用的语句在递归函数的最后一句，
==================

前几天做题也看到这个，只是当时没弄明白什么叫尾递归

#16

即使没有栈,
第归也可以改成非第归,
只是需要额外的内存(比如数组)来保存原来准备保存在栈里的相关信息而已.
当然使用栈是简明易懂的方式.

如果不允许使用额外内存空间,
则没有一个简单的办法可以进行判断.
不过,一般而言,
没有额外信息需要临时保存的第归(实际上栈并没有被使用),
都可以改成无栈并且不使用额外空间的非第归,
如果有额外的信息需要临时保存,并且信息量和第归深度成正相关的时候,
就不能改成无栈并且不使用额外空间的非第归。

第归本身就是一种使用栈保存临时信息的方式。

#17

没有办法可改，汉诺塔就是一个例子，不用递归根本解决不了的。

#18

只有尾递归可以直接消除递归！

其他的都需要间接的，如修改算法，栈保存参数和返回值全部或部分信息。

#19

什么情况下肯定可以把递归改成循环？

只有尾递归可以直接消除递归！就是循环就可以了

其他的都需要间接的，如修改算法，栈保存参数和返回值全部或部分信息。
比如：
F(0)=F(1)=1;
F(n) = n*F(n-1);

这个可以直接用循环实现

但是如果改为：
F(0)=F(1)=1;
F(n) = F(n-1)*n;

就不能直接消除递归，而需要修改算法，交换F(n-1) 与 n的位置。

如果用语法树来分析就明显了
{a}b
可用语法（1)
S->Ab
A->aA

上面的可以直接消除递归
下面文法（2)
S->Ab
A->Aa

这个就必须先消除左递归才行。

也就是LL（1）文法为什么先要消除左递归，再进行分析的原故。

#20

所有尾递归和一些特殊的非尾递归(如树的中序遍历)可以改

#21

这是hanoi非递归算法.

include <iostream> 
#include <stdlib.h> 

#ifdef _WIN32 
using namespace std; 
#endif 

static void hanoi(int height) 
{ 
    int fromPole, toPole, Disk; 
    int *BitStr = new int[height], 
        *Hold   = new int[height]; 
    char Place[]  = {'A', 'C', 'B'}; 
    int i, j, temp; 
  
    for (i=0; i < height; i++) 
    { 
        BitStr[i] = 0; 
        Hold[i] = 1; 
    } 
    temp = 3 - (height % 2); 
    int TotalMoves = (1 << height) - 1; 
    for (i=1; i <= TotalMoves; i++) 
    { 
        for (j=0 ; BitStr[j] != 0; j++) 
        { 
            BitStr[j] = 0; 
        } 
        BitStr[j] = 1; 
        Disk = j+1; 
        if (Disk == 1) 
        { 
            fromPole = Hold[0]; 
            toPole = 6 - fromPole - temp; 
            temp = fromPole; 
        } 
        else 
        { 
            fromPole = Hold[Disk-1]; 
            toPole = 6 - Hold[0] - Hold[Disk-1]; 
        }        
        cout << "Move disk " << Disk << " from " << Place[fromPole-1] 
             << " to " << Place[toPole-1] << endl; 
        Hold[Disk-1] = toPole; 
    } 
} 




int main(int argc, char *argv[]) 
{ 
    cout << "Towers of Hanoi: " << endl 
         << "moving a tower of n disks from pole A to pole B by using pole C" << endl; 
    cout << "Input the height of the original tower: "; 
    int height; 
    cin >> height; 
    hanoi(height); 

    system("PAUSE"); 
    return EXIT_SUCCESS; 
} 



问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1, 2, ..., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。 

算法要点有二： 
1、确定哪一个盘子要移动。有n个盘子的Hanoi塔需要移动2^n -1次，设m为n位的二进制数，则m的取值范围为0～2^n -1。让m每次递增1，可以发现，m中最低一位的刚刚由0变为1的位置的位置编号，和即将要移动的盘子编号有确定关系。 

2、这个盘子往哪个柱子上移。 
a.第一次需要移动1号盘，n为奇数时，1号盘首先移动到柱子B，为偶数时首先移动到柱子C。 
b.接下来如果移动的盘子不是1号盘。你有两个柱子可以选择。先找到1号盘所在的柱子，因为移动的盘子不能叠放到1号盘上，所以该盘可以移动的位置就是没有1号盘的那个柱子。 
c.如果移动的盘子是1号盘。也有两个柱子可以选择。找到1号盘原先是从哪个柱子上移来的，因为移动的顺序（顺时针或逆时针）一旦确定，就不会更改，所以排除from的那个柱子后，移动方向也就唯一了。 

#22

首先那要看你怎么理解递归.用栈对递归过程进行原始模拟，并没有从本质上改变递归算法的计算过程，但是如果以递归调用为形式的算法称为递归算法,其他的不是,那么模拟后的算法就不是递归算法,这也就可以说任何递归算法都是可以用非递归形式来实现.  

#23

另一种理解,用堆栈实现递归只是模拟了递归的计算过程,并没有消除递归,真正的非递归是指运算所需空间与问题的输入规模无关。当然尾递归可以用迭代来实现非递归,还有把递归转化为尾递归，再转化为迭代,例如用Cooper变换就可以把一大类的递归转化为尾递归。可是并不是所有的递归都可以用迭代实现，例如Ackmann函数就无法用迭代计算.其实正如当年海星所说,转换只是一种模拟，实际上是用人脑完成了电脑的某些过程.

#24

mark

#25

尾递归？
F(0)=F(1)=1;
F(n) = n*F(n-1);

和
F(0)=F(1)=1;
F(n) = F(n-1)*n
有区别吗？
没有区别，我认为。

#26

都可以改的，只是复杂程度能不能忍受而已

#27

   mark

#28

  都可以改的，只是复杂程度能不能忍受而已

----------正确！！

#29

yshuise() ( ) 信誉：100  2006-8-8 7:43:41  得分: 0  
尾递归？
F(0)=F(1)=1;
F(n) = n*F(n-1);

和
F(0)=F(1)=1;
F(n) = F(n-1)*n
有区别吗？
没有区别，我认为。
-----------------------------------------
对于较高层次来说，这当然没有区别，但是编译器就能识别这两者有本质的区别。语法数也截然不同

#30

对于较高层次来说，这当然没有区别，但是编译器就能识别这两者有本质的区别。语法数也截然不同
===
是这样。

#31

尾递归可以改为非递归

#32

最基本的程序结构,顺序,判断,循环,全部递归都可以被这三种结构表示。

#33

应该都可以改成非递归的。

#34

可以用数学的方法，来把 Hanoi问题，归结为，一个数学符号式子，然后用循环就可以解决。

#35

凡是递归都可以改成循环

#36

理论上所有的递归都可以改成非递归，如果改不了只能说明没想到．而且非递归要比递归省时间和空间，不过更费脑．