Recursive Fibonacci

lllllIllIlllI 0 206 Views

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))
Member Avatar for djidjadji
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)
Member Avatar for lllllIllIlllI
lllllIllIlllI 178 Veteran Poster

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

Member Avatar for sneekula
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.

Edited by sneekula because: n/a
Member Avatar for lllllIllIlllI
lllllIllIlllI 178 Veteran Poster

Hahaha, woops :P didnt see someone had already done it! :)

Member Avatar for sneekula
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.

Edit Preview