# Recursive Fibonacci

This code shows an example of using recursion to simply solve a problem. Note though, it can take a long time to do larger numbers such as the 50th fibonacci numbers this way.

Hope this helps! :)

``````#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)``````

Yeah, this was more to give an example of recursion. But some good points :)

sneekula 969

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.