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

Question

这是我目前的代码：

from loguru import logger

def fibonacci(n, s="% s"):
    """
    Using recursive method
    """
    # logger.debug(f"Finding {n}th Fibonacci number")
    logger.debug(s % ("fib(%d)" % (n)))

    a = 0
    b = 1

    if n <= 0:
        return a
    elif n in (1, 2):
        return b
    else:
        return fibonacci(n - 1,  s % ("fib(%d) + %%s" % (n - 1))) + fibonacci(n - 2, s % ("fib(%d) + %%s" % (n - 2)))

我的目标是在日志中显示递归树，例如＜code＞fibonacci（5）＜/code＞：

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
and so on...

这可能吗？当前代码没有产生预期的输出。

电流输出：

fib(5)
fib(4) + fib(4)
fib(4) + fib(3) + fib(3)
fib(4) + fib(3) + fib(2) + fib(2)
fib(4) + fib(3) + fib(1) + fib(1)
fib(4) + fib(2) + fib(2)
fib(3) + fib(3)
fib(3) + fib(2) + fib(2)
fib(3) + fib(1) + fib(1)

理念：

Answer 1

一种方法是，递归中的每个调用都可以将自身“报告”到其在树记录中的位置。然后我们可以逐级迭代。像这样：

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

Answer 2

您可以定义一个类来保存二叉树节点，并将树构建为递归fibonacci函数的结果:

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

您可以在这里找到< code>printBTree函数

如果只需要说明调用层次结构，可以直接使用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