如何在python上显示斐波那契递归树

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

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))
"""

您可以定义一个类来保存二叉树节点,并根据递归斐波那契函数构建树:

class BNode:
    def __init__(self,value,left=None,right=None):
        self.value = value
        self.left  = left
        self.right = right
        
    def print(self):
        printBTree(self,nodeInfo=lambda n:(str(n.value),n.left,n.right))

from functools import lru_cache

@lru_cache()                   # optimize object count
def fiboTree(n):               # (n is an index, not a count)
    if n<2: return BNode(n)
    a,b = fiboTree(n-2),fiboTree(n-1)
    return BNode(a.value+b.value,a,b)

输出:

fiboTree(7).print()

                       13
          ____________/  \____________
         5                            8
   _____/ \____               _______/ \______
  2            3             3                5
 / \        __/ \_        __/ \_        _____/ \____
1   1      1      2      1      2      2            3
   / \    / \    / \    / \    / \    / \        __/ \_
  0   1  0   1  1   1  0   1  1   1  1   1      1      2
                   / \           / \    / \    / \    / \
                  0   1         0   1  0   1  0   1  1   1
                                                        / \
                                                       0   1

你可以找到 printBTree 作用 here

如果只需要说明调用层次结构,可以直接使用printBTree函数:

def fibo(n):
    n=int(n) # linking with strings to let zero come out as a node
    return (f"fibo({n})",[None,str(n-2)][n>1], [None,str(n-1)][n>1])


printBTree(5,fibo)

                      fibo(5)
            ____________/ \____________
     fibo(3)                           fibo(4)
       / \                          _____/ \____
fibo(1)   fibo(2)            fibo(2)            fibo(3)
            / \                / \                / \
     fibo(0)   fibo(1)  fibo(0)   fibo(1)  fibo(1)   fibo(2)
                                                       / \
                                                fibo(0)   fibo(1)

为了边打印边打印,我建议使用缩进来传达调用层次结构,否则重复添加的内容将很难与调用方联系起来。

def fibo(n,indent=""):
    if n<2: return n
    print(indent[:-3] + "|_ "*bool(indent) 
          + f"fibo({n}) = fibo({n-2}) + fibo({n-1})")
    return fibo(n-2,indent+"|  ")+fibo(n-1,indent+"   ") 



fibo(7)

fibo(7) = fibo(5) + fibo(6)
|_ fibo(5) = fibo(3) + fibo(4)
|  |_ fibo(3) = fibo(1) + fibo(2)
|  |  |_ fibo(2) = fibo(0) + fibo(1)
|  |_ fibo(4) = fibo(2) + fibo(3)
|     |_ fibo(2) = fibo(0) + fibo(1)
|     |_ fibo(3) = fibo(1) + fibo(2)
|        |_ fibo(2) = fibo(0) + fibo(1)
|_ fibo(6) = fibo(4) + fibo(5)
   |_ fibo(4) = fibo(2) + fibo(3)
   |  |_ fibo(2) = fibo(0) + fibo(1)
   |  |_ fibo(3) = fibo(1) + fibo(2)
   |     |_ fibo(2) = fibo(0) + fibo(1)
   |_ fibo(5) = fibo(3) + fibo(4)
      |_ fibo(3) = fibo(1) + fibo(2)
      |  |_ fibo(2) = fibo(0) + fibo(1)
      |_ fibo(4) = fibo(2) + fibo(3)
         |_ fibo(2) = fibo(0) + fibo(1)
         |_ fibo(3) = fibo(1) + fibo(2)
            |_ fibo(2) = fibo(0) + fibo(1)

这可以说明记忆的好处/效果:

def fibo(n,indent="",memo=None):
    if n<2: return n
    if memo is None: memo = dict()
    print(indent[:-3] + "|_ "*bool(indent) + f"fibo({n})",end=" = ")
    if n in memo:
        print("taken from memo")
    else:
        print(f"fibo({n-2}) + fibo({n-1})")
        memo[n] = fibo(n-2,indent+"|  ",memo)+fibo(n-1,indent+"   ",memo)
    return memo[n]

fibo(7) = fibo(5) + fibo(6)
|_ fibo(5) = fibo(3) + fibo(4)
|  |_ fibo(3) = fibo(1) + fibo(2)
|  |  |_ fibo(2) = fibo(0) + fibo(1)
|  |_ fibo(4) = fibo(2) + fibo(3)
|     |_ fibo(2) = taken from memo
|     |_ fibo(3) = taken from memo
|_ fibo(6) = fibo(4) + fibo(5)
   |_ fibo(4) = taken from memo
   |_ fibo(5) = taken from memo