python - 如何在 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)))

我的目标是在日志中显示递归树，例如 fibonacci(5) :

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

您可以定义一个类来保存二叉树节点并构建树作为递归斐波那契函数的结果:

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