尾巴的Java

Question

/向前遞推我不明白爲什麼這是向前遞推：

int count(int x) { 
    if(x<=0) return 0; 
    return 1 + count(x - 1); 
} 

這是對模擬考試的問題時，得到的答覆是，其前向迭代。爲什麼會這樣？我怎麼能區分這兩者？

Answer 1

你正在做一個補充後自稱。尾遞歸的意思是絕對的沒有什麼可以在

如果你理解了實現，這是明確的原因。

假設我們從main第一次致電count，這是program counter0xAAA。然後它執行其大部分方法。我們會說這個堆棧幀的遞歸調用數爲0xBBB。如果您使用尾遞歸，在調用自身時，它可以將返回地址設置爲0xAAA（直接轉到調用我的代碼）。如果在之後的任何東西之後，它必須將返回地址設置爲0xBBC（加法的地址）。因爲它不需要堆棧幀來存儲返回地址，所以將遞歸轉換爲迭代也更容易。當count自己調用時，它可以跳轉到方法的開頭。

該解決方案（在簡單的例子）是建立在結果的另一個參數：

int count(int x, int res) { 
    if(x<=0) return res; 
    return count(x - 1, res + 1); 
} 

注意，我們以後什麼也不做。

Answer 2

你看過this SO question, tail vs forward recursion嗎？

馬修有了答案，而長表將是：

int count(int x) { 
    if(x<=0) return 0; 
    return 1 + count(x - 1); 
} 

可以寫爲（和擴展爲類似）：

int count(int x) { 
    if(x<=0) return 0; 
    int tmp_result = count(x - 1); 
    return 1 + tmp_result; // e.g. recursion is not last 
}