Fast recursive function for returning n-th Fibonacci number

You probably missed the fact that this function returns two results: One as its return value and one in the "input" parameter passed by reference.

The severe inefficiency of the simple recursive definition of fib is that at each recursive level you must make two different calls to lower levels, even though one of them includes all the work of the other.

By allowing the one that includes all the work of the "other" to also return the result of the "other", you avoid doubling the work at each level.

In the mathematical sense it is no longer a "function" (because of the side effect). But as a function in the programming sense, it sidesteps the efficiency problem of fib by returning two values from one call.

I think it appropriate to mention that in C++, there are more elegant ways to return a pair of values as the result of a function. (Even in C you could return a struct by value).

Edit (in response to your edit):

The main thing I cannot grasp is what does fib(n – 1, prev0) return when we have garbage stored in prev0.

The trick is that prev0 is an output from the function, not an input.

I am a beginner, so, please, be as specific as you can.

The parameter declaration of int & in the function signature lets the function use that parameter as input or output or both as it chooses. This particular function uses it as output.

If you understand the basics of recursive functions, you understand how each level of the recursion has its own copy of the parameter n and of the local variable prev0. But prev1 is not a separate variable. It is effectively an alias for the higher level's prev0. So any read or write of the current level's prev1 really happens to the higher level's prev0.

This level's n is passed "by value" meaning it is a copy of the value of the passed expression (the higher level's n-1 ). But this level's prev1 is passed by reference so it is not a copy of the value of the higher level's prev0, it is an alias of the higher level's prev0.

Note that prev1 is never read from. Only written to. Let's think about the function this way:

std::pair<int,int> fib_pair(int n) {
    if (n < 2) {
        return std::make_pair(n, 0);
    }

    std::pair<int, int> prev = fib_pair(n-1);
    return std::make_pair(prev.first + prev.second, prev.first);
}

Now it's clearer - there's the one recursive call, and fib(n) returns the two previous numbers, instead of just the one. As a result, we have a linear function instead of an exponential one. We can then rewrite the original version in terms of this one to help us understand both:

int fib(int n, int &prev1) {
    std::pair<int, int> pair = fib_pair(n);
    prev1 = pair.second;
    return pair.first;
}

Let's look at four different functions that compute the nth fibonacci number, using pseudocode instead of restricting the program to a single language. The first follows the standard recursive definition:

function fib(n) # exponential
    if n <= 2 return 1
    return fib(n-1) + fib(n-2)

This function requires exponential time, O(2ⁿ), because it recomputes previously-computed fibonacci numbers at each step. The second function requires linear time, O(n), by working from 1 to n instead of n to 1 and keeping track of the two previous fibonacci numbers:

function fib(n) # linear
    if n <= 2 return 1
    prev2 = prev1 = 1
    k := 3
    while k <= n
        fib := prev2 + prev1
        prev2 := prev1
        prev1 := fib
    return fib

That's the same algorithm your program uses, though yours disguises what's going on by operating recursively and passing one of the parameters by a pointer to a variable in an outer scope.

Dijkstra described an algorithm for computing the n fibonacci number in logarithmic time, O(log n), using matrices and the exponentiation by squaring algorithm. I won't give the full explanation here; Dijkstra does it better than I could (though you should beware his convention that F₀ = 1 instead of F₀ = 0 as we have been doing it). Here's the algorithm:

function fib(n) # logarithmic
    if n <= 2 return 1
    n2 := n // 2 # integer division
    if n % 2 == 1 return square(fib(n2+1)) + square(fib(n2))
    return fib(n2) * (2*fib(n2-1) + fib(n2))

The fourth algorithm operates in constant time, O(1), provided you have floating-point numbers with sufficient precision, using the mathematical definition of the fibonacci numbers:

function fib(n) # constant
    sqrt5 := sqrt(5)
    p := (1 + sqrt5) / 2
    q := 1 / p
    return floor((p**n + q**n) / sqrt5 + 0.5)

For most languages this last algorithm isn't very useful, because for fibonacci numbers of any size you need some kind of unlimited-precision decimal arithmetic library, and although it's constant time it will probably take longer in practice than the simple logarithmic-time algorithm operating on unlimited-precision integers, at least until n is very large.

The obvious (non efficient) implementation of finding a Fibonacci number would be:

int fib(int n) {
    if (n<2) return n;
    return fib(n-2) + fib(n-1);
}

This implementation is inefficient you are doing the same calculations twice.

For example if n is 6, you the algorithm would tell you to add fib(4) and fib(5). To find fib(5), you need to add fib(4) and fib(3). And there you go calculating fib(4) for the second time. As n becomes larger, this will become more inefficient.

The example you provided avoids this inefficiency by remembering the previous fibonacci sequence.