There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply () below!

Agree with a comment or answer? Like () to up-vote the contribution!

One way to count recursions is with a dictionary created in the global space.

fib_dict = {}
def fibonacci(n, p):
fib_dict[p] += 1 # uptate the value by 1 for each trip into the function
if n < 2:
return n
else:
return fibonacci(n-1, p) + fibonacci(n-2, p)
for n in range(1, 50):
fib_dict[n] = 0
trial_base = 1.6
print(n, fibonacci(n, n), fib_dict[n], trial_base**n, trial_base**n - fib_dict[n] )

The extra parameter p is needed to keep the dict key constant as n changes for a given set of recursions. It looks to me like it’s a bit less than O(2^N), maybe 1.6xx^N??

Following the hint, I created a dictionary to store Fibonacci values with the aim of increasing the efficiency of the function. The way I managed this syntactically was to create a Fibonacci class. With a class structure, the .fibonacci() method can refer to a class counter and a class dictionary to keep track of the total number of function calls (a measure of efficiency, as I understand) and already-calculated values for given n.

I’m amazed at how much more efficient the class version of the function is. For example, finding the value of the 20th element in the Fibonacci sequence required 39 function calls with this method, and 21,891 without the storage dictionary. (Or do I have something wrong and is that too good to be true?)

class Fibonacci:
def __init__(self, n):
self.store = {0: 0, 1: 1}
self.counter = 0
def fibonacci(self, n):
self.counter += 1
if n in self.store.keys():
return self.store[n]
else:
result = self.fibonacci(n-1) + self.fibonacci(n-2)
self.store[n] = result
return result

Unless this table is going to be repeatedly polled and possibly extended, it would not be feasible, imho. In a strictly algorithmic sense, we only need to keep two values afloat to arrive at the third, which then becomes the second, and the second becomes the first. Essentially we’re climbing a ladder and the only rungs that matter are this one and the next one.

In so doing, we never take up more memory to find a number very high up the ladder than we would a rather low one. Kudos on your discovery, though. Well done.

I agree. Actually, I think it is the golden ratio going on here.
The runtime is 1.6180… ^N.

Interesting that you got to the same result in a different way.
The way I looked at it, the number of calls you have to make for calculating F_n is the number of calls you have to make to calculate F_(n-1) + the number of calls you have to make to calculate F_(n-2) plus one. So denoting K_n to be the number of calls you have to make to calculate the nth Fibonacci number, you get
K_n = K_(n-1) + K_(n-2) + 1
This is a second order inhomogen difference equation. Once you solve it and strip away all the smaller terms, the most important term is the golden ratio to the power n.
I think? Correct me if I am wrong.

I’m afraid I’ll not be able to contribute anything on difference equations, but, yes, come to think of it, most discussions of Fibonacci quickly invoke the golden ratio, so I’d certainly agree. Thanks for the input.

Hi, i dont know why my code when using memoization yields the same number of recursive iterations compared to the one where I dont use a dictionary to keep track of the already calculated fibonacci numbers… I cant figure it out…

def fibonacci(n):
memo = {0:0, 1:1}
if n in memo.keys():
return memo[n]
else:
print("Recursive call with {0} as input".format(n))
result = fibonacci(n - 1) + fibonacci(n - 2)
memo[n] = result
return result

I think it is because the variable memo has only a local scope. When another function call occurs, another memo is newly defined as a different variable. So it does not retain the value of memo defined by the previous function call.

Hi,
First of all. Thank you patrick for sharing the class
and text for the runtime input. I was intrigued.
I had a different approach as well and I came to the same solution

Memoization sounds great… but I’m really scratching my head as to why my version doesn’t calculate the correct numbers! Everything is correct til the 4th number, which returns 4 instead of 3. The next few results are higher than they should be, after that, they’re lower…

Does anybody see the error? I feel like it’s staring me in the face, but the code is essentially the same as @chsgray 's.

fibonacci_correct = {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55}
memo = {0: 0, 1: 1}
def fibonacci(n):
if n in memo.keys():
return memo[n]
else:
result = fibonacci(n - 1) + (n - 2)
print("#{} is {}. Adding to memo... (Should be {})".format(n, result, fibonacci_correct[n]))
memo[n] = result
return result
print(fibonacci(10))

Output:

#2 is 1. Adding to memo... (Should be 1)
#3 is 2. Adding to memo... (Should be 2)
#4 is 4. Adding to memo... (Should be 3)
#5 is 7. Adding to memo... (Should be 5)
#6 is 11. Adding to memo... (Should be 8)
#7 is 16. Adding to memo... (Should be 13)
#8 is 22. Adding to memo... (Should be 21)
#9 is 29. Adding to memo... (Should be 34)
#10 is 37. Adding to memo... (Should be 55)
37

Novel as it may be, memoization of this sequence is pointless. It doesn’t rely upon the full sequence of terms, just the last two. They are memoized in their respective a, b variables.

>>> def fib(n):
a, b = 0, 1
for i in range(1, n):
a, b = b, a + b
return a
>>> fib(1)
0
>>> fib(2)
1
>>> fib(3)
1
>>> fib(4)
2
>>> fib(5)
3
>>> fib(6)
5
>>> fib(-1)
0
>>> fib(-10)
0
>>>

>>> n = 20
>>> [fib(x) for x in range(1, n)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
>>>

I don’t really understand this line: return fibonacci(n - 1) + fibonacci(n - 2)
If this ran: fibonacci(3)
Then would this happen: return fibonacci(2) + fibonacci(1)
In fibonacci(2): return fibonacci(1) + fibonacci(0)
Which resolves to 1 + 0 = 1.
In fibonacci(1):
which resolves to 1 fibonacci(3) return value: 1 + 1 = 2
Also I don’t know the Big O runtime.

I feel dumb I don’t understand what is going on here.

def fibonacci(n):
if n < 2:
return n
print(n-1, n-2)
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(14))
# set the appropriate runtime:
# 1, logN, N, N^2, 2^N, N!
fibonacci_runtime = "2^N"

where does the calculation occur? what I see is:
call fib with value 14
it’s not under 2, so:
return value of fib 13+12
which is return value of 12 + 11 AND 11 + 10
which is return value of 11 + 10 AND 10+9 AND 10+9 AND 9+8
and so on until:
return value of 1 and 0.

But where/how did it count?

edit: I just realized that it grows the further into the execution: is the last step before 0 is returned actually a sequence of values that summed up equals to the correct value for the nth Fibonacci number??

I was fasinated by how the code could be such clean. Just one quesiton, does it still count as a recursive function?

At the part of:

for i in range(1, n):
a, b = b, a + b

It seems like they’re adding on themselves, whihc is recursive in my point of view. But it’s not like the other recursive function I’ve learned which would contain a function itself inside the funciton.