Building the Fibonacci Sequence

The Fibonacci sequence is a common problem that can be solved with recursion (though a loop will be much more efficient). The Fibonacci sequence starts with 0 and 1, then all subsequent terms are equal to the sum of the previous two terms. So the start of the sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. In designing a recursive Fibonacci function, we can pass in the position in the sequence, and then have it calculate and return the value at that position. Position 0 will have value 0, and position 1 will have value 1, all other values can be calculated based upon the values at the previous two positions.

Tip

Notice that the definition of the Fibonacci sequence is recursive.

Function	Fibonaaci
Parameters	n: The position in the sequence to get the value for.
Returns	int: The value of the nth number in the Fibonacci sequence.
Description	Calculates and returns a value from the Fibonacci sequence.

Specification for the print line procedure

Have a go at building a recursive function to calculate a value from the Fibonacci sequence. Here is some starter code that you can use to build out this function:

#include "splashkit.h"

/**
 * This function calculates the Fibonacci number at a given position.
 *
 * @param n the position in the Fibonacci sequence
 * @return int the Fibonacci number at position n
 */
int fibonacci(int n)
{
    //TODO: implement this
    return 0;
}

int main()
{
  return 0;
}

Add in base cases

Have a go at identifying the base cases, these should be relatively straightforward to identify from the description. Add these to the fibonacci function and test that this works for calculating these numbers in the sequence.

• Identified base cases

  We have two base cases based on the value of position: 0 and 1. In these cases we can just return the value of the position itself.

  /**
   * This function calculates the Fibonacci number at a given position.
   *
   * @param n the position in the Fibonacci sequence
   * @return int the Fibonacci number at position n
   */
  int fibonacci(int n)
  {
      if (n < 2)
      {
          return n;
      }
      //TODO: implement this
      return 0;
  }
  
  int main()
  {
      write_line(fibonacci(0));
      write_line(fibonacci(1));
  
      return 0;
  }

Implementing the recursive case

Now add in the recursive code. Remember that this must move toward the base cases, and that you may need multiple recursive calls in this instance.

• Recursive case

  /**
   * This function calculates the Fibonacci number at a given position.
   *
   * @param n the position in the Fibonacci sequence
   * @return int the Fibonacci number at position n
   */
  int fibonacci(int n)
  {
      if (n < 2)
      {
          return n;
      }
      else
      {
          return fibonacci(n - 2) + fibonacci(n - 1);
      }
  }
  
  int main()
  {
      for(int i = 0; i < 10; i++)
      {
          write_line(fibonacci(i));
      }
  
      return 0;
  }

Testing your solution

Make sure to double-check the values you get from your solution. Check that this works for a range of values. What happens if we ask for a value at a negative position?

Thinking about efficiency

The code for this is relatively simple, and matches the definition of the recursive Fibonacci sequence. But it is always good to think about the efficiency of this. Think through what happens when you ask for fibonacci(4). How many times does it need to calculate fibonacci(2)? Now imagine how many steps are involved in calculating fibonacci(6).

To see this inefficiency, add a write_line statement inside the start of your fibonacci function as shown below. Now just calculate fibonacci(10) and have a look at what you get out.

#include "splashkit.h"

using std::to_string;

/**
 * This function calculates the Fibonacci number at a given position.
 *
 * @param n the position in the Fibonacci sequence
 * @return int the Fibonacci number at position n
 */
int fibonacci(int n)
{
    write_line("Calculating fibonacci " + to_string(n));
    //...
}

int main()
{
    write_line(fibonacci(6));

    return 0;
}

The version using a loop will be much more efficient. To implement this with a loop, you will need to keep track of the last two terms in separate variables. You may either have a separate next term variable, or reuse one of the existing variables. We leave this as an exercise for you to do yourself if you want.