再帰呼び出しが 1 回しかない再帰関数は、通常、あまり労力をかけずに末尾再帰関数に変換できます。その後、それを反復関数に変換するのは簡単です。ここでの標準的な例は階乗です。
# naïve recursion
def fac(n):
if n <= 1:
return 1
else:
return n * fac(n - 1)
# tail-recursive with accumulator
def fac(n):
def fac_helper(m, k):
if m <= 1:
return k
else:
return fac_helper(m - 1, m * k)
return fac_helper(n, 1)
# iterative with accumulator
def fac(n):
k = 1
while n > 1:
n, k = n - 1, n * k
return k
ただし、ここでのケースには 2 つの再帰呼び出しが含まれており、アルゴリズムを大幅に作り直さない限り、スタックを保持する必要があります。独自のスタックを管理することは、Python の関数呼び出しスタックを使用するよりも少し速いかもしれませんが、追加された速度と深さはおそらく複雑さに見合うものではありません. ここでの標準的な例は、フィボナッチ数列です。
# naïve recursion
def fib(n):
if n <= 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
# tail-recursive with accumulator and stack
def fib(n):
def fib_helper(m, k, stack):
if m <= 1:
if stack:
m = stack.pop()
return fib_helper(m, k + 1, stack)
else:
return k + 1
else:
stack.append(m - 2)
return fib_helper(m - 1, k, stack)
return fib_helper(n, 0, [])
# iterative with accumulator and stack
def fib(n):
k, stack = 0, []
while 1:
if n <= 1:
k = k + 1
if stack:
n = stack.pop()
else:
break
else:
stack.append(n - 2)
n = n - 1
return k
さて、あなたのケースはこれよりもはるかに困難です: 単純なアキュムレータでは、サブツリーを生成する必要がある場所へのポインターを使用して、部分的に構築されたツリーを表現するのが困難になります。ジッパーが必要になります。Python のような実際には機能しない言語で実装するのは簡単ではありません。
