C++ Tutorial => Using tail recursion and Fibonnaci-style recursion...

Example

The simple and most obvious way to use recursion to get the Nth term of the Fibonnaci sequence is this

int get_term_fib(int n)
{
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return get_term_fib(n - 1) + get_term_fib(n - 2);
}

However, this algorithm does not scale for higher terms: for bigger and bigger n, the number of function calls that you need to make grows exponentially. This can be replaced with a simple tail recursion.

int get_term_fib(int n, int prev = 0, int curr = 1)
{
  if (n == 0)
    return prev;
  if (n == 1)
    return curr;
  return get_term_fib(n - 1, curr, prev + curr);
}

Each call to the function now immediately calculates the next term in the Fibonnaci sequence, so the number of function calls scales linearly with n.

PDF - Download C++ for free

Previous Next

C++

Fastest Entity Framework Extensions

Example

Got any C++ Question?

C++

C++ Recursion in C++ Using tail recursion and Fibonnaci-style recursion to solve the Fibonnaci sequence

Fastest Entity Framework Extensions

Example

Got any C++ Question?