How do I show the fibonacci recursive tree on python

Question

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:

The parentheses indicate that its the child of previous node. You can see how I wrapped `fib(4)` into `fib(4) = fib(3) + fib(2)`. Refer the image. — user6308605, Oct 23 '21 at 13:03

Alain T. · Answer 1 · 2021-10-23T17:51:20.847

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)

This can illustrate the benefits/effect of memoization:

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

Cool tree printing function! – גלעד ברקן Oct 23 '21 at 14:14 — גלעד ברקן, Oct 23 '21 at 14:14
Very cool and thorough! Thank you so much – user6308605 Oct 24 '21 at 00:13 — user6308605, Oct 24 '21 at 00:13

גלעד ברקן · Accepted Answer · 2021-10-23T13:39:03.287

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

How do I show the fibonacci recursive tree on python

2 Answers2