C++ Recursion – Fibonacci

The Fibonacci Sequence

• Introduction to Recursion in C++

Fibonacci is a well known number sequence that models the growth of a rabbit population amongst other things found in nature.

Below is the Fibonacci numbers computed up to the 11th term.

Iterative version of Fibonacci

Fibonacci Formula

Fibonacci(0) = 0;
Fibonacci(1) = 1;
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2);

So how would we do an iterative version? I’ll walk you through the code.

1
2
3
4
5
6
7
8
9
10
11
12
13

// The value of n is the Fibonacci number we want to compute //
int fibonacci(int n) { 
 
    //Our two initial values
    int fib1 = 0;
    int fib2 = 1; 
 
    //Our running value
    int fib = fib1;
 
    // Computing the nth value of Fibonacci //
 
   return fib;

So how would we compute the value of the nth value of the Fibonacci sequence? We can do it with a for loop, to add UP to the value we are looking for. In other words, if we were doing it by hand, we’d do it as following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//Initial cases
fib(0) = 0;
fib(1) = 1;
 
fib(2) = fib(1) + fib(0) = 1 + 0 = 1;
 
fib(3) = fib(2) + fib(1) = 1 + 1 = 2;
 
fib(4) = fib(3) + fib(2) = 2 + 1 = 3;
 
fib(5) = fib(4) + fib(3) = 3 + 2 = 5; 
 
fib(6) = fib(5) + fib(3) = 5 + 3 = 8;
 
..
 
fib(n) = fib(n - 1) + fib(n-2);

You could think of fib(n), fib(n-1), and fib(n-2) being fib, fib1, and fib2 respectively in our code. Try coming up with a solution to compute the nth Fibonacci number.

The code to compute the Fibonacci sequence for iterative version is below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// The value of n is the Fibonacci number we want to compute //
int fibonacci(int n) { 
 
    //Our two initial values
    int fib1 = 0;
    int fib2 = 1; 
 
    //Our running value
    int fib = fib1;
 
    // Computing the nth value of Fibonacci //
    for ( int i = 1; i < n; i++ ) 
    { 
        // Fib(n) = fib(n-1) + fib(n-2);
        fib = fib1 + fib2;
 
        // The next two numbers are set this way 
        // to be used in the next computation of fib(n) 
        // Work it out by hand if you don't understand it.
 
        // Fib(n-1) = fib(n-2)
        // Fib(n-2) = fib
        fib1 = fib2;
 
        fib2 = fib;
    }
 
   // Return result
   return fib;

Recursive version Fibonacci

Fibonacci Formula

Fibonacci(0) = 0;
Fibonacci(1) = 1;
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2);

So let’s start by creating the base case and function header.

1
2
3
4
5
6
7

int fibonacci(int n) {
 
    // Base cases
    if ( n == 0 ) return 0;
    else if ( n == 1 ) return 1;
 
}

That was quite simple wasn’t it? An image describing the function calls are below.

So how do we go on by computing the nth term of the Fibonacci sequence? Try it out on your own first then come back. If you translated the formula correctly into code, it should then look like the following.

1
2
3
4
5
6
7
8
9
10
11

int fibonacci(int n) {
 
    // Base cases
    if ( n == 0 ) return 0;
    else if ( n == 1 ) return 1;
 
    //This is returning fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
    else 
         return fibonacci(n-1) + fibonacci(n-2);
 
}

Explanation of Fibonacci using Recursion

The following image shows you how the recursive calls would be made with larger n values.

Overview of Fibonacci Sequence using Recursion

If you have any questions or suggestions, feel free to post them below.

Related Posts

• C++ Recursion – Reverse elements of a vector (0)
• C++ Recursion – Power Continued (0)
• C++ Recursion – Power (1)
• Fibonacci in C++ (3)
• C++ Recursion – Palindrome (0)
• C++ Recursion – Factorial (0)
• C++ Recursion – Summation (2)
• Introduction to Recursion in C++ (6)
• C++ Recursion (0)
• C++ Recursion – Greatest Common Divisor (0)