如何檢測根遞歸調用？

假設我們正在編寫一個簡單的遞歸函數fib(n)來計算第n個斐波納契數。現在，我們希望該功能打印該第n個數字。由於同一個函數被重複調用，必須有一個條件只允許打印根呼叫。問題是：如何在不傳遞任何附加參數或使用全局/靜態變量的情況下編寫此條件。如何檢測根遞歸調用？

所以，我們正在處理的是這樣的：

int fib(int n) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2) + fib(n-1); 
    if(???) cout << fn << endl; 
    return fn; 
} 

int main() { 
    fib(5); 
    return 0; 
}

我認爲根本的呼叫通過返回到不同的來電者，即本例中的主要方法，從所有的孩子不同。我想知道是否有可能使用此屬性來編寫條件和方式。

更新：請注意，這是一個人爲設計的例子，僅用於介紹該想法。這應該從標籤中清楚。我不尋找標準的解決方案。謝謝。

來源

2010-04-22 Ahmed Abdelkader

正如許多答案中指出的那樣，創建一個啓動遞歸的包裝函數是很常見的做法。自定義之前/之後處理（如IO）可以去那裏。 – 2010-04-22 16:18:45

我會做到這一點的方法是使用一個輔助功能：

int _fib(int n) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = _fib(n-2) + _fib(n-1); 
    return fn; 
} 

int fib(int n) { 
    int fn=_fib(n); 
    cout << fn << endl; 
    return fn; 
}

或者，你可以像這樣（C++）寫：

int fib(int n, bool f=true) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2, false) + fib(n-1, false); 
    if(f) cout << fn << endl; 
    return fn; 
}

來源

2010-04-22 16:13:04 Blindy

不錯的一個。我暫時忘了默認參數。 – 2010-04-22 16:17:36

順便說一句，你的第一個解決方案不是打印一切嗎？似乎函數_fib應該調用它自己，而不是fib。 – Feyyaz 2010-04-22 16:33:03

呃yea，小錯字：p – Blindy 2010-04-22 16:58:32

根遞歸調用是遞歸被調用的點，即在main中的調用。鑑於這種情況，你可以重寫你的代碼稍微（像這樣）：

int fib(int n) { 
    if(n <= 0) return 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2) + fib(n-1); 
    return fn; 
} 

int main() { 
    cout << fib(5) << endl; 
    return 0; 
}

來源

2010-04-22 16:08:08 fbrereto

又來了一個取巧的辦法，雖然我不知道這是值得的:)：

int fib(int n) { 
// if(n <= 0) return 0; 
    int isRoot; 
    if (n <= 0){ 
     isRoot = 1; 
     n = -n; 
    } 
    else isRoot = 0; 
    int fn = 1; 
    if(n > 2) fn = fib(n-2) + fib(n-1); 
    if(isRoot) cout << fn << endl; 
    return fn; 
} 

int main() { 
    fib(-5); 
    return 0; 
}

但是，在函數要求你不要真的意味着發送一個負值:)。

來源

2010-04-22 16:08:24 Feyyaz

如果你真的要問清楚是否ç可以訪問某種類型的API，它允許函數體中的代碼從執行函數的調用中找出答案，答案是no。

來源

2010-04-22 16:18:36 reinierpost

沒問題，但是*你*（和程序員一樣）可以裝飾呼叫以找出它們來自哪裏。 – Blindy 2010-04-22 16:20:13

其他答案已經涵蓋了。 – reinierpost 2010-04-23 10:12:57

我想你可以從堆棧中獲得返回地址，並以某種方式與fib函數的地址進行比較。返回地址應該在接近參數n的地方，除非n在某個寄存器中傳遞，但在標準C中它不應該。您只需知道返回地址與參數的相對位置。

來源

2010-04-22 17:06:57

如何檢測根遞歸調用？

回答

相關問題