老师摆不平它，就靠高手了！。。。

在学数据结构时，有一问题：
怎样把递归程序变成非递归的？？？
是不是都能变成非递归的？
具体点：
求此问题的非递归算法：

akm(m,n)=:
  1.  n+1 :(m=0)
  2.  akm(m-1,1):(m!=0 && n==0)
  3.  akm(m-1, akm(m,n-1)):(m!=0 && n!=0)
此问题要求用栈实现！
我发现是双递归，我想不出，各位帮帮忙把。

10 个解决方案

#1

所有递归的问题均可以用栈实现，你以上问题实现非递归，你可以通过看递归的实现过程加以解决

#2

可以用两个栈实现

#3

递归到底是什么？是说函数的嵌套使用，还是说一种解题方法？

#4

用一个栈就可以了!
你可看IBM汇编( 清华)的习题册.

#5

你的问题问的不明确，
递归化非递归有两种方式，一种是利用堆栈，这实际上还是递归，只不过本来由编译器帮你做的事由你自己用代码来实现了，所以更本不能算非递归；
另一种则是根据问题的实质，利用数学知识将递归转化为递推，但是不是所有的递归问题都有其递推形式的，比如你所给的这个akman函数，已经可以从数学上证明这个函数没有递推形式。
对于某一类的递归问题，可以用固定的方法将其转化为递推形式。比如利用cook定理，可以将一大类的递归问题转化为尾递归，然后再转化为递推。关于这方面说起来也比较复杂，建议你看看程序设计方法学方面的书（可不是指OO方法之类的程序设计方法哦，我说的是那种形式化的程序设计方法研究方面的书）

#6

另外，这个ackman函数如果用堆栈模拟递归其实很简单，你想想看普通的递归程序怎么写，然后在该程序段的开头和结尾部分自己手工压栈出栈就可以了
对于普通的递归函数，有通用的固定模式可以将它转化为手工设置堆栈的形式

#7

mark

#8

//一个栈可不可以这样
long akm(int m,int n)
{
stack s;
do
{
if(m==0)
{
if(!s.isEmpty())
{
m=s.pop();
n++;
}
else return n+1;
}
else
if(n==0)
{
m--;n=1;
}
else{
s.push(m-1);n--;
}
}while(1);
}

#9

经典问题，but 2 old.

int Ackerman(int m, int n)
{
   STACK s[MAX];
   int top = 0; //top 始终指向m的值，并不是指向栈顶（栈顶是n的值）而是指向次栈顶
   s[top] = m;
   s[top+1] = n;
   do
   {
      if (s[top]==0)       {
                             s[top]=s[top+1]+1;
                             top--;
                           }
      else if (s[top+1]==0){
                             s[top]=s[top]-1;
                             s[top+1]=1;
                           }
      else                 {
                             s[top+2]=s[top+1]-1;
                             s[top+1]=s[top];
                             s[top]--;
                             top++;
                           }
   }while(top>=0);
   return s[0];
}

#10

to starfish(海星)　;
能否推荐一本？
谢谢！

#1