Рекурсивная функция с одним рекурсивным вызовом обычно может быть превращена в хвостовую рекурсивную функцию без особых усилий, и тогда ее просто преобразовать в итеративную функцию. Канонический пример здесь факториален:
# 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
Однако ваш случай здесь включает два рекурсивных вызова, и, если вы существенно не переделали свой алгоритм, вам нужно сохранить стек. Управление вашим собственным стеком может быть немного быстрее, чем использование стека вызовов функций 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.