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 . Its roots are , the golden ratio and .

There is a solution of the form: . From the initial conditions: and . Hence, we have

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`

.