如何计算这漫长的递归

下面是一个代码做递归出故障了较大的值：如何计算这漫长的递归

int rec(int m,int n)  
{ 
    if(m==0) 
     return n+1; 
    if(m>0 && n==0) 
     return rec(m-1,1); 
    if(m>0 && n>0) 
     return rec(m-1,rec(m,n-1)); 
}

如果我调用该函数rec(m,n)：

与m=1和n=2，结果我得到是4
与m=2和n=2，它是7,
与m=3和n=2，它是29

但崩溃为m=4和m=2。有没有其他的方法来计算它？

来源

2014-03-02 dabs

这是阿克曼的功能吗？：D – Dejan

那你有什么问题？你想知道*为什么它崩溃，你想让它为（4，2）工作吗？还有别的吗？ – delnan

是的，这是阿克曼的功能。 – dabs

阿克曼的功能可以被非递归表示为

确认（M，N）=（2 OP_米（N + 3）） - 3-

其中op_米是第m次加法，乘法，乘幂，塔函数的算术运算，...

换句话说，它爆炸的价值相当麻烦瞬间，与没办法将这些数字表示为C++整数。

有关说明见我的主页从1990年的:)，（http://web.archive.org/web/20120315031240/http://members.fortunecity.com/alf_steinbach/content/programming/narrow_topics/ackermann/ackermann.html）

来源

2014-03-02 14:04:34

rec(4,2) 
-> rec(3, rec(4, 1)) 
      ->rec(3, rec(4, 0) 
        ->rec(3, 1) 
        ->rec(2, rec(3, 0)) 
          ->rec(2, 1) 
          ->rec(1, rec(2, 0))    -->rec(1, 2) //return 4 
            ->rec(1, 0) //return 2  -->rec(0, rec(1, 1)) //return 4 
            ->rec(0, 1) //return 2    -->rec(0, rec(1, 0)) //return 3 
                        -->return 2

将此归结为：

rec(4,2) 
-> rec(3, rec(4, 1)) 
      ->rec(3, rec(4, 0) 
        ->rec(3, 1) 
        ->rec(2, rec(3, 0)) 
          ->rec(2, 1) 
          ->rec(1, 4)

这可以进一步解决，但空间不足，将需要很多时间。我预测你的应用程序或者由于stackoverflow或者由于达到允许的递归限制而崩溃。但我不能肯定地说... @Cheers和hth。 - 阿尔夫以更微妙的方式在数学上解释它;）

来源

2014-03-02 14:07:36

当然你不是试图写出A（4，2）的调用图吗？如果你不先生气，你可能会达到（非常慷慨的）答案长度限制。 – delnan

最初我以为我可以归结为递归的结束，但现在我明白了这是怎么回事。所以现在就停下来...... :) –

+1为智能通信的尝试。 ;-) –

如何计算这漫长的递归

回答

相关问题