#Using recursion to get fibonacci numbers

#Our getFib function, needs a whole number
def getFib(number):
    
    #assert the number is whole
    assert(isinstance(number,int)),"Needs a whole number"

    #Base case. When the number is 1
    #we know what we want to return
    #so there is no need for more recursion
    #we can just return our value
    if number == 1 or number ==0:
        return 1
  

    #For any number apart from 1
    #we do another recursion of the program
    #this will happen until number == 1
    else:
        return getFib(number-1)+getFib(number-2)

    
print("10th fibonacci number: %i" %getFib(10))
print("20th fibonacci number: %i" %getFib(20))

It takes a long time because many fib-numbers are calculated a lot.
If you store the numbers you already know it goes pretty fast.
And these results are stored for the duration of the program so the next call to getFib(50) is instantaneous
Use a class variable to store the known fib-numbers and give the class static methods.
Assign these static methods to other names for readability.
If you use a wrapper function you only have to test the assert statement once.

# 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]
        except KeyError:
            result = FibonacciStorage._fib(number-1) + FibonacciStorage._fib(number-2)
            FibonacciStorage._storage[number] = result
            return result
    @staticmethod
    def fib(number):
        # 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(20)

You can also read up on Fibonacci numbers here:
http://www.daniweb.com/code/snippet216645.html
Mentions the slow recursive function and the faster generator function.
BTW, the generator function is 25,000 times faster than the recursive function when calculating the first 30 members of the Fibonacci series.

Edited 7 Years Ago by sneekula: n/a

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.