2
\$\begingroup\$

I wrote code to show the structure of a Fibonacci sequence pattern in a graphical way. First I structure a tree given a variable the user inputs for how many iterations of the sequence they want to print. Then, it converts the numbers into the Fibonacci sequence.

My concern is that this doesn't seem very efficient, first I build a tree, then go through each node again and do the entire Fibonacci calculation on it. Instead, I was hoping for a suggestion to change the code so that it could generate the nodes and the Fibonacci number at the same time. Maybe, instead of two recursive functions, there is just one that calls itself:

fibo(num)=fibo(num-1)+fibo(num-2)

where (num-1) is the left node and (num-2) is on the right.

from binarytree import Node

 # Generates a binarytree with the correct *iterations* numbers.
def makeTree(node):
    if node.value > 1:
        node.left = makeTree(Node(node.value - 1))
        node.right = makeTree(Node(node.value - 2))
    return node

 # Converts the iterated binary tree numbers into fibonacci numbers
def fibonacci(a, b , num):
    if num > 0:
        a += b
        return fibonacci(b, a, num - 1) 
    return a

a = int(input("Enter number: "))
fibTree = makeTree(Node(a))

for x in fibTree:
    x.value = fibonacci(0, 1, x.value)

print(fibTree)

Expected result if a user enters 5 as how many iterations they want.

fibo seq console log

\$\endgroup\$
1
\$\begingroup\$

One thing I would recommend is using memoization. Make a dictionary of fibonacci numbers that you've already calculated (do the math once when the user gives you input). When you go to calculate a node's fibonacci value, just do a check in the dictionary for the appropriate value. This will avoid calculating the lower levels so much.
Actually, if you only know the level the node is on, you could instead put the fibonacci values in an array (python list) where the index of the array is the number that should be shown on that level of the tree. Either way, there are ways to use memoization to avoid duplicate effort, and it can make a big difference in your speed for a lot of problems.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.