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! :)
Recursive Fibonacci
#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))
djidjadji 28 Light Poster
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) lllllIllIlllI 178 Veteran Poster
Yeah, this was more to give an example of recursion. But some good points :)
sneekula 969 Nearly a Posting Maven
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.
lllllIllIlllI 178 Veteran Poster
Hahaha, woops :P didnt see someone had already done it! :)
sneekula 969 Nearly a Posting Maven
Fibonacci numbers and prime numbers are always a hot topic! Your contribution is welcome!
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.