A well-known sequence

April 12, 2017


A child is running up a staircase with n steps and can hop either one step or two steps at a time. How many possible ways the child can run up the stairs?


The top down approach

Suppose that the child is on the nth steps, with n>1. The child could have done either a single or a double step hop. That is, he might have hopped from the stair n-2 or n-1.

The total number of ways is therefore the sum of the number of ways of reaching stair n-2 and n-1. That gives us a sequence only determined by the two first numbers. Hence, we have:

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

The complexity is exponential because of the fact that for each computation, the function needs two recursive calls. Worse, the function is unnecessary computed with the same input many times. The total number of recursive calls is equal to the result.

> ./fib 45
1134903170
Elapsed time: 8564364 clocks, 8564.364 milliseconds

To improve the time calculation, we can use memoization: if the function was already called with the same input, we just recall the result, otherwise we stock the result into the array.

long long mem[100];
long long fibMem(int n) {
  if (mem[n]) return mem[n];
  if (n == 0) {
    return mem[0] = 0;
  }
  if (n == 1) {
    return mem[1] = 1;
  }
  return mem[n] = fibMem(n-2) + fibMem(n-1);
}
> ./fibMem 45
1134903170
Elapsed time: 26 clocks, 0.026 milliseconds.

Analysis

The associate characteristic equation is figure 4 . Its roots are figure 5 , the golden ratio and figure 6 .

There is a solution of the form: figure 9 . From the initial conditions: figure 10 and figure 11 . Hence, we have figure 8

For n big enough, we can calculate the nth fibonacci number like this:

long long fibCalc(int n) {
  return floor((1/sqrt(5)) * pow((1 + sqrt(5))/2, n));
}

However, when n is too big, the precision does not yield the right result. The first wrong calculation is for n=72: 498454011879264 instead of 498454011879265.

cactus

References:

  1. Fibonacci number - en.wikipedia.org
  2. Computing the Fibonacci numbers - chaos.org.uk
  3. Golden ratio - en.wikipedia.org