Python中的嵌套遞歸函數

Question

我試圖在Python中實現一個嵌套的遞歸函數它給出了一個錯誤「RuntimeError：最大遞歸深度超出」，你可以在下面的代碼中看到該函數。你對這個問題的幫助表示讚賞。遞歸

n=10 

def test(n): 
    if n<=0: 
     return 1 
    else: 
     return test(test(n-1)+1) 

print test(n) 

Answer 1

一個非常重要的部分是與每一個遞歸調用，你必須得到接近到你的錨的情況下，在這種情況下是：

if n<=0: 
    return 1 

然而，隨着你的代碼沒有接近這種情況。問題是這樣的一行：

return test(test(n-1)+1) 

由於測試返回1當它到達結束的情況下，你加1，這個結果，讓我們看看當我們調用會發生什麼test(2)：

錨的情況下是不執行，你直接進入else。您回覆

test(test(1)+1) 

自2-1=1。你內心的測試呼叫也要去到else情況，並呼籲：

test(test(0)+1) 

這裏你內心的測試呼叫返回1（它已經到達終點的情況下），這意味着，基本上在這條線，你在呼喚

test(2) //test(1+1) 

再次。在這裏你可以看到你的遞歸永不結束，因此你的maximum recursion depth exceeded error。

只是爲了澄清你怎麼能做出這樣的代碼（這顯然只是一個例子）工作：

def test(n): 
    if n <= 0: 
     return 1 
    else: 
     return test(test(n-1)-1) //notice the -1 instead of +1 

後續問題：

爲什麼改變遞歸調用測試（測試（N -2））也導致無限遞歸？

那麼這基本上是因爲我在開始時就指出了同樣的道理。你需要接近你的主播案例。雖然您可以在嵌套的遞歸調用test(n-2)內達到n<=0的情況，但您肯定無法在外部函數調用中達到它。

注意，你的函數，當它到達它的結束的情況下，這樣即使test(n-2)不會引起任何更多的遞歸則返回1（不是0）返回1，這意味着你最終

test(1) 

這會再次造成無限循環（因爲您無法將n作爲此外部函數調用的<= 0）。

對於這種情況，您有多個選項可以使遞歸工作：通過更改返回值或更改錨點大小寫。因此，改變if語句要麼這些都將阻止無限遞歸：

if n <= 0: 
    return 0 

或

if n <= 1: 
    return 1 //you could also return any other value <= 1