調用本身返回兩次 - 尾遞歸還是不是？

我理解尾遞歸，但我已被分配編寫代碼來查看第N個斐波那契數是什麼。開始，這段代碼確實有效。這不是最好的方式，但它是一種方式 - 但是我開始擔心它不是尾遞歸。該代碼是在這裏：調用本身返回兩次 - 尾遞歸還是不是？

static int fib_tail_helper(int n, int result) { 
if (n == 0) { 
    return result; 
} 
else if (result == 0) { 
    return fib_tail_helper(n - 1, result + 1); 
} 
else { 
    return fib_tail_helper(n - 1, result + fib_tail_helper(n - 1, 0)); 
} 
} 

int fib_tail(int n) { 
/* 
// REQUIRES: n >= 0 
// EFFECTS: computes the Nth Fibonacci number 
//   fib(0) = 0 
//   fib(1) = 1 
//   fib(n) = fib(n-1) + fib(n-2) for (n>1). 
// MUST be tail recursive 
*/ 
return fib_tail_helper(n, 0); 
}

我主要是擔心「迴歸fib_tail_helper（N - 1，結果+ fib_tail_helper（N - 1），0」我覺得，如果將使用另一種。棧，從而成爲非尾遞歸...誰能給一些輸入？

謝謝！

來源

2014-09-19 MrKevKev

如果你想確定檢查編譯器輸出。 – dtech 2014-09-19 23:07:32

不，它不是尾遞歸。

編譯器需要評估fib_tail_helper argume nt首先，這意味着它會創建n-1個調用堆棧，然後繼續調用最後的fib_tail_helper作爲返回值。

來源

2014-09-19 23:16:04 ArunasR

要說明的是這不是尾遞歸轉換可能會有所幫助：

static int fib_tail_helper(int n, int result) { 
    if (n == 0) { 
     return result; 
    } 
    else if (result == 0) { 
     return fib_tail_helper(n - 1, result + 1); 
    } 
    else { 
     int tailrecursivePreventingValue = fib_tail_helper(n - 1, 0); 
     return fib_tail_helper(n - 1, result + tailrecursivePreventingValue); 
    } 
}

它確實完全一樣，你的代碼，但引入了一個解釋變量。你可以看到在最後的else塊中有2個調用fib_tail_helper（）。這意味着指數運行時間，因爲第二個值取決於第一個值。

來源

2014-09-20 01:39:56 Markus

尾遞歸是一個巧妙的遞歸實現，它不使用堆棧空間。

它的工作原理是這樣的：
如果一個函數自己調用它，因爲它是最後一個動作，那就叫做「尾遞歸」。
在這種特殊情況下，編譯器可以放棄執行實際的函數調用。它可以執行一個goto回到函數的開頭。函數的代碼將再次運行，就像它已被調用一樣。當函數終止時，它將返回到棧上的最後一個地址，這是最初稱爲遞歸函數的函數。

這種方法保證堆棧不會溢出，不管遞歸有多深。這就是關於尾遞歸的偉大之處。

壞消息是C++不會自動支持尾遞歸。

好消息是，實現尾遞歸非常容易。
您只需將最後的函數調用用goto替換回函數的開頭。
（這只是你編寫goto，編譯器會支持，如果它支持尾遞歸。）

來源

2014-09-20 02:43:03

調用本身返回兩次 - 尾遞歸還是不是？

回答

相關問題