גלעד ברקן

一种方法是递归中的每个调用“报告”自己在树记录中的位置。然后我们可以逐级迭代。比如:

def f(n):
  t = ["None"] * (2**(n-1) + 1)
 
  def g(n, i):
    l = "(" if i & 1 else ""
    r = ")" if not (i & 1) else ""
    t[i] = "%sfib(%s)%s" % (l, n, r)
 
    if n > 1:
      g(n-1, 2*i+1)
      g(n-2, 2*i+2)
 
  g(n, 0)
 
  print(t[0][0:-1])
  i = 1
  while 2**i-1 < len(t):
    print(" + ".join(t[2**i-1:2**(i+1)-1]))
    i += 1

输出:

f(5)

"""
fib(5)
(fib(4) + fib(3))
(fib(3) + fib(2)) + (fib(2) + fib(1))
(fib(2) + fib(1)) + (fib(1) + fib(0)) + (fib(1) + fib(0)) + None + None
(fib(1) + fib(0))
"""