Unable to understand recursion and caching from Fibonacci code

Question

I try to understand recursion and caching much better, and yet I make interesting progress (sometimes I'm a little slow). I have slight problems understanding this code:

# Fibonacci recursive with result storage class FibonacciStorage: _storage = { 0:1, 1:1 } @staticmethod def _fib(number): try: # is this already calculated return FibonacciStorage._storage[number] #searches dict, and if value exists then return it except KeyError: result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2) #this is the actual Fibonacci Formula FibonacciStorage._storage[number] = result #adds result to dictionary #print FibonacciStorage._storage #this shows the storage list growing with each iteration. return result @staticmethod def fib(number): #first function, it has two asserts to basically make sure number is whole/positive and if its okay passes it to _fib(where the real work is done) # only do the assert statements once assert(isinstance(number,int)),"Needs a whole number" assert(number>0),"Needs a positive whole number" return FibonacciStorage._fib(number) # use a more readable name getFib = FibonacciStorage.fib print getFib(50) 

I found this code on the net and tried to comment out each line to understand what it actually does. I don’t understand how this recursion is, it executes a code loop until the correct result is specified, but I don’t see how to call it myself.

At first, I thought it was a line: result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2) , but I'm confused because my print FibonacciStorage._storage line print FibonacciStorage._storage shows that the cache storage is growing and growing but the line below it is a return function. I suspect I don’t understand how the return result actually somehow starts the recursion again.

I'm also not sure how the storage dictionary makes this program so fast. My simple fiber sequence recursions take a lot of time (even when I save the data), but in this case, if you execute print getFib(200) its instant. How does caching do this so fast?

So to summarize, two questions:

1) How does recursion work? Should my print statement access each cycle?

2) How does caching speed it up over other sequences of fibers? Is the class structure or @staticmethod excellent? For example, this seems instantaneous, while those at http://en.literateprograms.org/Fibonacci_numbers_(Python ) have a slight delay.

3) Maybe, also because of the interval, can the alpha-type fibnocci scale (split and work in parallel) only because of interference or is limited to one process?

Any insight would be helpful.

Answer 1

(1) The recursive call is on this line:

 result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2) // here ^ and here ^ 

You are right, this is the “actual Fibonacci formula”, which by definition is recursive.

(2) Caching speeds it up. What difference is there a permanent _storage object that saves you an impressive amount of duplicate actions. Consider:

  fib(4) / \ fib(3) + fib(2) / \ / \ fib(2) + fib(1) fib(1) + fib(0) / \ fib(1) + fib(0) 

This is just fib(4) and you can already see the redundancy. By simply caching the integer values fib(3) and fib(4) you reduce the number of calculations needed for fib(5) from 7 to 1. And the savings will only grow as you move.

Answer 2

The Fibonacci implementation in question uses the memoization method to store the already calculated values ​​and efficiently retrieve them every time they are needed, rather than recounting them. This has a huge performance advantage since values ​​need to be calculated only once.

About your questions:

• The recursion starts on this line: FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2) , as you can see, the _fib procedure calls itself
• Caching greatly improves computing speed; see this example for a full explanation of how this works. Using static methods in this case is not particularly useful, it only makes the implementation more invented.
• A recursive, non-memoized version can be split into a parallel algorithm, where each fibonacci call is made in a different thread. However, the overhead would be significant, and the algorithmic complexity would not improve at all. Stick to the memoized version or read about faster ways to calculate fibonacci.

Answer 3

It's good to know that Python dicts has a __missing__ method that is called for missing keys:

 class FibonacciStorage(dict): def __missing__(self, n): self[n] = self[n - 1] + self[n - 2] return self[n] 

Using:

 fib = FibonacciStorage({0: 1, 1: 1}) print(fib[50]) #20365011074