How do I show the fibonacci recursive tree on python-CodePudding

This is my code currently:

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

My goal is to show the recursive tree in the log such as for fibonacci(5):

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

Is this possible? Current code didn't produce the expected output.

Current output:

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)

The idea:

CodePudding user response：

One way could be for each call in the recursion to "report" itself to its location in a record of the tree. Then we can iterate level by level. Something like:

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

Output:

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

CodePudding user response：

You could define a class to hold binary tree nodes and build the tree as the result of the recursive fibonacci function:

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)

Output:

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

You can find the printBTree function here

If you only need to illustrate the call hierarchy, you can use the printBTree function directly:

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)

To print as you go, I would suggest using indentation to convey the call hierarchy otherwise the repeated additions will be hard to relate to their callers.

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)