Solution Review : Compute nth Fibonacci Number

This lesson will explain how to compute the nth Fibonacci number using recursion.

We'll cover the following

Solution: Use Recursion

The Fibonacci sequence is obtained by adding the previous two consecutive terms; they are defined by the sequence,

fibonacci(0) = 0 # base case 
fibonacci(1) = 1 

fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2) for n >= 2 # recursive case

For example ,


if n=2, f(n)=3

The following illustration explains the concept by calculating the fourth Fibonacci number.

The following python code demonstrates how to find the nth fibonacci number:

def fibonacci(n):
if n <= 1:
return n
return(fibonacci(n-1) + fibonacci(n-2))

Let’s move on to the next problem.