Dynamic programming

Sometimes, recursively defined functions can be very expensive; especially if the same function is being calculated over and over again. We will look at two such problems:

1. Calculating the Fibonacci numbers, and
2. calculating the binomial coefficients.

In this lesson, we will look at calculating the Fibonacci numbers.

Suppose you implement the Fibonacci numbers as follows:

#include <iostream>
unsigned long fibonacci( unsigned long n );
int main();

unsigned long fibonacci( unsigned long n ) {
	if ( n == 0 ) {
		return 0;
	else if ( n <= 2 ) {
		return 1;
	} else {
		return fibonacci( n - 1 ) + fibonacci( n - 2 );
	}
}

int main() {
	for ( unsigned long n{0}; n <= 100; ++n ) {
		std::cout << "fibonacci(" << n << ") = "
		          << fibonacci( n ) << std::endl;
	}

	return 0;
}

How long does it take to execute this program? (Hint: give up sooner than it ends, please...)

How long would it take you to calculate the 42nd Fibonacci number? How would you calculate it? How many local variables do you need? What type of loop would you use?

Write a function that calculates the $n$^th Fibonacci number where it is very fast to calculate that the $93$^th Fibonacci number is $12200160415121876738$. Is your result for the $94$^th Fibonacci number correct? Why or why not?

Hint: this author can write a function that quickly calculates the $n$^th Fibonacci number using only two local variables. It is, however, easier to do this with four local variables where one of the variables is the index of the for-loop and another is a temporary local variable.

In the next lesson, you will look at calculating the binomial coefficients.