如何計算這漫長的遞歸

下面是一個代碼做遞歸出故障了較大的值：如何計算這漫長的遞歸

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爲智能通信的嘗試。 ;-) –

如何計算這漫長的遞歸

回答

相關問題