Fibonacci sequence is a very well-known sequence which takes its name from the mathematician Fibonacci who proposed the formula for the calculation of the growth of a population of rabbits. The growth was idealized because the behaviors were deterministic and the death of the rabbits was not taken into account but the sequence is still relevant today and one of the reason is the strong relationship with the Golden Ratio number.

Some of the sequence' values are $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$ so, the sequence begins with $F_0=0$ and $F_1=1$, then all the other numbers of the sequence are the sum of the previous two numbers: for example $F_2=F_1+F_0=1+0=1$, then $F_3=F_2+F_1=1+1=2$, then $F_4=F_3+F_2=2+1=3$, and so on. In general, the n-th number of the sequence is $F_n=F_{n-1}+F_{n-2}$.

Fibonacci is typically also used in programming as an example of recursive functions given its natural recursive formula (i.e. every new value depends on previous values). The code provided assumes a knowledge on how to create functions and recursive functions in Python, if required click the button below to gain some insights about these topics.

Intro to Functions in Python

The code defines a function called Fibonacci: the input of this function is the term $n$ of the sequence while the output is the n-th Fibonacci number. Then, the function is pretty straightforward and follows the mathematical equation: the first term should be 0, the second term should be 1 and any other term should be the sum of previous terms which call again the Fibonacci function.

def Fibonacci(n):
	if(n==0):     # First term is 0
		return 0
	elif(n==1):   # Second term is 1
		return 1
	else:         # Any other term is the sum of previous two terms
		return Fibonacci(n-1)+Fibonacci(n-2)

print(Fibonacci(4))  # Print 4th Fibonacci Number
print(Fibonacci(9))  # Print 9th Fibonacci Number

It is possible to write the function in a more compact way because in case of $n=0$ and $n=1$ the sequence simply returns $n$ as shown below.

def Fibonacci(n):
	if(n <= 1):   # If n is 0 or 1 return n
		return n
	else:         # Any other term is the sum of previous two terms
		return Fibonacci(n-1)+Fibonacci(n-2)

print(Fibonacci(4))  # Print 4th Fibonacci Number
print(Fibonacci(9))  # Print 9th Fibonacci Number

If we run this function in the console below we see that for $n=4$ the Fibonacci number is $3$ and for $n=9$ the Fibonacci number is $34$. The section below shows how the Fibonacci sequence can be written also iteratively without the need of using recursion.

The iterative version of the Fibonacci sequence needs a loop which continues until the n-th term of the sequence is calculated. In particular two terms are changed in the for loop, term1 and term2: term2 is saved in a temporary variable, term2 becomes the sum of both terms (i.e. effectively becomes term3) and then term1 is updated with the value of the temporary variable. This loop is repeated until the $n-th$ term is created and then it is returned.

def Fibonacci_Iter(n):
	fib_n1=0    # First term is 0
	fib_n2=1    # Second term is 1
	for i in range(n):   # Loop up to the n-th term
		temp=fib_n2      # Save second term in a temporary variable
		fib_n2=fib_n1+fib_n2  # Update second term to third term (sum of 2 terms)
		fib_n1=temp      # First term becomes second term
	return fib_n1        # Return the updated first term

print(Fibonacci_Iter(4))  # Print 4th Fibonacci Number
print(Fibonacci_Iter(9))  # Print 9th Fibonacci Number	

Use the console below to test different input values and also try to modify this function to achieve the same goal.

	r/ValianTek_World
Iterative and Recursive Fibonacci in Python
|View Comments|Write Comments|