Learn the best way to calculate Fibonacci numbers with this python program, as well as the recursive implementation.
There is an interesting application of Fibonacci numbers. Consider that there is an idealized rabbit population. Newborn rabbits start mating in one month. And at the end of the second month, they produce another pair of rabbits. Assuming the rabbits never die, and they continue reproducing forever, how many pairs they will be in a certain period? Read more about some applications here.
Even though the previous application is unrealistic, it can help you calculate an approximate rabbit production for a short period.
The mathematic definition of Fibonacci numbers is as follows:
f(0)=0
f(1)=1
f(n) = f(n-1) + f(n-2), n>1
So, let’s get to it.
Python program to calculate Fibonacci numbers using recursion
The recursive version of this program is not the most efficient one. But we should take every opportunity that comes our way to practice.
As you should know, recursion is a very important tool in programming, so let’s practice.
The three aspects we must consider, when creating a program using recursion are as follows:
- Basic case, a.k.a. stop condition. In this case, is when n=0 or n=1
- Divide the problem into smaller-input problems. We calculate f(n-1) and f(n-2)
Combine the solutions of the smaller-input problems to get the solution to the original problem. In this case, we combine the smaller-input solution by adding them (fibonacci(n-1) + fibonacci(n-2))
And now we are ready to implement the function that will return the Fibonacci of a number.
def fibonacci(n):
if n == 0 or n==1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
Efficient Python program to calculate Fibonacci numbers
As you should know by now, having knowledge of mathematics can give you a great advantage in programming.
You guess it right. We can use mathematics to improve the efficiency of calculating a Fibonacci number.
If you know how to solve Linear Homogeneous Recurrence Relations with Constant Coefficients, which is the case of the Fibonacci sequence, you can find a formula that will give you the Fibonacci number.
What is the meaning of this? It means that we can have a (non-recurrent) formula to find out the result. The time-complexity of this new algorithm will be O(1). This means the numbers can be calculated in constant time.
See below the code.
def iterative_fibonacci(n):
sqrt5 = 5**0.5
phi = ( 1 + sqrt5 ) / 2
psi = ( 1 - sqrt5 ) / 2
return int ((phi ** n - psi ** n) / sqrt5)
From now, anytime you are asked to calculate a Fibonacci number, you should use this implementation. It is the efficient way of calculating such numbers.
You can use the main program above to test the two implementations.
if __name__=='__main__':
n = int(input('Enter a non negative number: '))
print(fibonacci(n))
print(iterative_fibonacci(n))
H@ppy coding.
Related posts: