嵌套遞歸是可能的還是應該避免遞歸？

F（1）= 1
F（2N）= F（n）的
F（2N + 1）= F（N）+ F（ N + 1）

開發的遞歸程序來計算F

一些用戶採用兩個遞歸函數調用提到：

def calc(n): 
    if n=1 : 
    return 1 
    else if(n%2)==0: 
    return calc(n/2) 
    else : 
    return calc(n/2)+calc(n/2+1) **NESTED RECURSION**

這是一個正確的邏輯嗎？算法不會是指數級的大嗎？我想到了一個簡單的代碼，如：

def calc(count): 
    result[1]=1 
    n=2 
    for range(1,count): 
     if n%2=0: 
      result.append(result[n]) 
     else : 
      result.append(result[n/2]+result[n/2+1]) 
    return result

來源

2011-01-19 Nishant

`高清鈣（N）： IF ... ELSE：回報計算的（N/2）+計算值（N/2 + 1）`不是嵌套的，只是重複。試試[Ackermann]（https://en.wikipedia.org/wiki/Ackermann_function）。 – greybeard 2017-11-04 10:28:43

這兩種方法都是正確的。從一個函數中進行多次遞歸調用確實是合法的，其意義就是你想的 - 只需要一個調用，然後是下一個，然後是下一個等。

有趣的是，我不認爲遞歸版本確實使指數級的多次調用成爲可能。它最多可以進行兩次遞歸調用，但每個調用都會遇到一個問題，其大小約爲原始調用的一半。從本質上講，復發看起來是這樣的：

T(1) = 1 
T(2) = 1 
T(n) <= T(n/2) + T(n/2 + 1) + 1

我使用「小於或等於這裏」說，在最好的情況下，你可能只是做出一個電話，但在最壞的情況下，你讓最多兩個。

我想證明一些常數c，d和a的函數T（n）< = max {cn + d，a}。這將證明T（n）= O（n）並因此使得最多線性地多次調用。由於我們的基本情況，我們有

T(1) = 1 
T(2) = 1

所以讓我們設置一個= 1。對於歸納步，我們考慮三種情況。首先，讓我們時地板（N/2）< = 2和地板（N/2 + 1）< = 2的考慮：

T(n) <= T(n/2) + T(n/2 + 1) + 1 
    <= 1 + 1 + 1 
    <= 3

如果我們假設CN + d> = 3，當n = 3或n = 4，那麼這個解決正確。尤其是，這意味着3c + d> = 3和4c + d> = 3。

在下一個案例中，讓我們看看樓層（n/2）< = 2和floor（n/2 + 1）> = 2。然後，我們有

T(n) <= T(n/2) + T(n/2 + 1) + 1 
    <= 1 + max{c(n/2 + 1) + d, 1} + 1 
    <= 2 + max{c(n/2 + 1) + d, 1} 
    <= 3 + c(n/2 + 1) + d

因此，如果我們有一個3 + C（N/2 + 1）+ d < = CN + d，這要求仍然成立。請注意，我們只能是在這種情況下，如果n = 5，所以這意味着我們必須有

3 + c(n/2 + 1) + d <= cn + d 
3 + c(n/2 + 1)  <= cn 
3 + c(5/2 + 1)  <= 5c 
3 + 5c/2 + c   <= 5c 
3 + 7c/2    <= 5c 
4     <= 3c/2 
8/3    <= c

因此，我們必須有C> = 8/3

最後，情況下既沒有N/2也不N/2 + 1是少於三個：

T(n) <= T(n/2) + T(n/2 + 1) + 1 
    <= c(n/2) + d + c(n/2 + 1) + d + 1 
    <= cn/2 + cn/2 + c + 2d + 1 
     = cn + c + 2d + 1

這是小於CN + d如果

cn + c + 2d + 1 <= cn + d 
     c + 2d + 1 <=  d 
     c + d + 1 <= 0

這WOR ks if d = -c - 1.

從前面我們知道3c + d> = 3，如果2c-1> = 3，或者2c> = 4，那麼c> = 2。有圖4c + d> = 3，如果c> = 2讓C = 8/3，我們得到這也適用的是d = -11/3，所以

T(n) <= max{8n/3 - 11/3, 1}

所以T（n）的= O （n）並且遞歸只能線性地處理很多調用。

這個簡短的版本是，遞歸和迭代版本都需要線性時間。不要擔心遞歸的指數時間爆炸而不確定它是指數的。 :-)雖然承認，在這種情況下，我更喜歡迭代版本。它更清晰，更直觀，更立即O（n）。

來源

2011-01-19 22:23:24 templatetypedef

什麼解釋，我會讀它肯定:)我在這個noob。 – Nishant 2011-01-19 22:25:08

@ Nishant-希望我沒有弄錯數學。 :-) – templatetypedef 2011-01-19 22:26:27

遞歸也不錯。將遞歸看作是一種工具。有些問題可以用遞歸（如斐波那契數）很好地解決，而其他問題沒有遞歸彎曲（工作列表類型算法）。

爲什麼人們在遞歸時出錯是因爲他們認爲遞歸解決方案會給他們一個良好的聲譽。我會說，用最簡單的方法解決問題。

有時候這種方法是遞歸的，有時候不是。

此外，遞歸方法可能更難以理解。所以，你需要考慮可讀性。

來源

2011-01-19 22:07:37 Davidann

估計第二個算法的性能比較容易：它顯然是空間和時間上的O（n），而且是一個很小的常量。但這並不意味着第二種算法比第一種算法更快。其實它不是！

在Python 2.6.5，你的第二算法是25X 比第一慢在計算calc(1000)，80X較慢處計算calc(65535)計算calc(10000)，和1712x慢。

第一種算法的最壞情況行爲似乎是54613 = 1101010101010101 這樣的數字。對於這個值，第一個算法只比第二個算法快16倍。

在簡單的遞歸算法，calc(1000)只涉及50調用calc，甚至calc(54613)只有5166.

這需要O（log n）的算法仍然較快：

def C(x): 
    a = 1 
    b = 0 
    # Loop invariant: we are going to return a*C(x) + b*C(x + 1). 
    while x >= 2: 
     if x % 2 == 0: 
      a += b 
     else: 
      b += a 
     x //= 2 
    return a + b

的性能這個算法很容易評估，但它的正確性不是。 ;-)

來源

2011-01-19 22:59:34

實際上，您可以編寫一個次線性的遞歸版本（O（log n））。

關鍵是要注意，如果給定[n/2]和[n/2] +1的兩個值，您可以計算出兩個的n值和n + 1值。所以如果你將兩個值看作是一個元組T（n）=（F（n），F（n + 1）），那麼給定T（[n/2]），你可以計算T（n）中。

所以你的函數將會像

Tuple F(int n) { 
    // Base cases: 

    Tuple result; 
    if (n is even) { 
     Tuple t = F(n/2); 
     result.First = t.First; 
     result.Second =t.First + t.Second; 

     return result; 
    } 

    if (n is odd) { 

     Tuple t = F((n-1)/2); 
     result.First = t.First + t.Second; 
     result.Second = t.Second; 
     return result; 
    } 
}

這樣你最終使剛剛一個遞歸調用，因爲你減半輸入的大小爲每個呼叫，它是遞歸和 O（ LOGN）。

練習：使用這個技巧給出斐波納契數字的O（log n）時間算法。

提示：使用身份：

alt text

來源

2011-01-20 03:34:36

嵌套遞歸是可能的還是應該避免遞歸？

回答

相關問題