區分簡單遞歸和多遞歸

Question

我們的教授要求我們去Distinguish between simple and multiple recursion，我不確定我是否理解正確。

從我所知，多次遞歸是當一個方法在他的生命週期中被調用多次（例如斐波那契），但是簡單的遞歸呢？是否僅僅調用一次方法？如果你能舉個例子嗎？

這是教授。問題

Answer 1

單呼叫遞歸的典型例子是階乘函數：

f(n) = n * (n-1) * (n-2) ... * 3 * 2 * 1 

這將被實現爲僞代碼：

def factorial (int n, assert n > 0): 
    if n == 1: 
     return 1 
    return n * factorial (n - 1)   # one call 

對比度與天真斐波那契發生器：

def fib (int n, assert n >= 0): 
    if n < 2: 
     return 1 
    return fib (n - 1) + fib (n - 2)  # two calls 

---

維基百科從而定義了這些術語，雖然使用single而非simple，這使得在對比multiple更有意義：

單遞歸和多個遞歸

遞歸只包含單個自引用稱爲單遞歸，而包含多個自引用的遞歸是kno作爲多次遞歸。

單遞歸的標準示例包括列表遍歷，例如在線性搜索中，或者計算階乘函數，而多次遞歸的標準示例包括樹遍歷，比如在深度優先搜索中，或者計算斐波那契數列。

---

不真的一個很好的使用情況遞歸因爲有大量的在每個呼叫的反覆努力。迭代求解好得多在這種情況下（代碼是長一點，但工作量最小化）：

def fib (int n, assert n >= 0): 
    if n < 2: 
     return 1 
    n = n - 2 

    grandparent = 1 
    parent = 1 
    me = grandparent + parent 
    while n > 0: 
     n = n - 1 
     grandparent = parent 
     parent = me 
     me = grandparent + parent 
    return me