Pythonのネストされた再帰関数

Question

Pythonでネストされた再帰関数を実装しようとしましたが、 "RuntimeError：最大再帰深度を超過しました"というエラーが表示されます。質問に対するあなたの助けに感謝します。

再帰の1つの非常に重要な部分は、すべての再帰呼び出しを使用すると、このケースでは、あなたのアンカーケースに 近づく必要があるということです

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です。ちょうどあなたがこのコードを作ることができる方法を明確にする

は、（明らかに単なる一例である）仕事：

はなぜ（テスト（nはテストするために再帰呼び出しを変更しない：

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

は質問をフォローアップ-2））もまた無限再帰をもたらすでしょうか？

これは基本的に私が最初に正しく指摘したのと同じ理由があるためです。アンカーケースに近づく必要があります。ネストされた再帰呼び出しtest(n-2)の内部でn<=0のケースに達することができますが、確かに外側の関数呼び出しの内部に到達することはできません。それがエンドケースなのでtest(n-2)が、それ以上の再帰が発生しない場合でも、それはあなたが

test(1) 

で終わることを意味する、1（0ではない）を返し達したときに、あなたの関数が1を返すこと

注意（この外部関数呼び出しのためにnを<= 0にすることができないので）無限ループを引き起こします。

このケースで再帰を行うには、複数のオプションがあります。戻り値を変更するか、アンカーケースを変更します。（

if n <= 0: 
    return 0 

または

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