再帰とバインディング

Question

再帰を使用する方法を理解しようとしていますが、少し問題があります。

ローカル変数を使用しようとすると、毎回関数の先頭で再帰が開始されるため、値がリセットされます（= []は毎回空のリストにリセットされます） 。

値を保持しながら（たとえば、リストに値を追加した場合など）再帰を完了し、その値をローカルレベル（関数内）に保持する方法はありますか？

Answer 1

私はこれを処理するために2つの異なる方法があります。各例ではリスト[1, 2, 3, 4]が作成されます。

最初の手法では、最初は空のデフォルトの引数を使用しますが、後でアキュムレータをより深い呼び出しに渡すために使用されます。

def build_range(n, accumulator=None): 
    accumulator = accumulator or [] 
    if n == 0: 
     return accumulator 

    accumulator.insert(0, n) 
    return build_range(n-1, accumulator) 

print build_range(4) # [1, 2, 3, 4] 

第2のアプローチでは、リスト連結を使用して、小さなリストを合計してリストを構築します。このアプローチは、新しいものを構築する必要がなくなり、不変なデータ型がより洗練されているので、リストではあまり効果がないことに注意してください。

次に、3番目の非再帰的アプローチは、ループに再帰するようにアンロールすることです。

def build_range(n): 
    accumulator = [] 
    while n: 
     accumulator.insert(0, n) 
     n -= 1 
    return accumulator 

print build_range(4) # [1, 2, 3, 4] 

明らかに、これは後方範囲を構築するの拷問、非効率的な例のようなものである（挿入はアペンド未満理想的です）、うまくいけば、それは全体のアイデアを取得します。

Answer 2

あなたが理解しているものとそうでないものが本当に明確ではないので、答えは難しい質問です。 @JaredGoguenはあなたに様々なテクニックを見せてくれる素敵な試みをしました。私はそれにカップルを追加したい

この実装では、補助的な再帰関数を使用しています。 Jaredの2番目の実装と同様に動作しますが、そのテールコールのために、トランポリンに乗ってスタックを安全にすることができます。これは、少なくとも90％の時間で再帰プロシージャを実装する方法です。

def build_range (n): 
    def aux (m, acc): 
    if m == n: 
     return acc 
    else: 
     return aux(m + 1, acc + [m]) 
    return aux(0, []) 

print(build_range(4)) 
# [0, 1, 2, 3] 

この手法の別のバリエーションは、アキュムレータとしてラムダを使用することです。これは、保留中の結果をスタックに保持しなくても、順方向にイテレートを構築する場合に特に便利です。ここでも、理由は末尾呼び出しの、些細な変更は、トランポリンを利用し、それはあなたが再帰的ステップで、関数を呼び出し、引数として渡す安全

def map (f, xs): 
    def aux(xs, k): 
    if not xs: 
     return k([]) 
    else: 
     return aux(xs[1:], lambda ys: k([f(xs[0])] + ys)) 
    return aux(xs, lambda x: x) 

print(map(lambda x: x * x, [1,2,3,4])) 
# [1, 4, 9, 16]