Fibonacci using Recursion

Question

This is my idea of solving 'nth term of fibonacci series with least processing power'-

int fibo(int n, int a, int b){
    return (n>0) ? fibo(n-1, b, a+b) : a;
}

main(){
    printf("5th term of fibo is %d", fibo(5 - 1, 0, 1));
}

To print all the terms, till nth term,

int fibo(int n, int a, int b){
    printf("%d ", a);
    return (n>0)? fibo(n-1, b, a+b): a;
}

I showed this code to my university professor and as per her, this is a wrong approach to solve Fibonacci problem as this does not abstract the method. I should have the function to be called as fibo(n) and not fibo(n, 0, 1). This wasn't a satisfactory answer to me, so I thought of asking experts on SOF.

It has its own advantage over traditional methods of solving Fibonacci problems. The technique where we employ two parallel recursions to get nth term of Fibonacci (fibo(n-1) + fibo(n-2)) might be slow to give 100th term of the series whereas my technique will be lot faster even in the worst scenario.

To abstract it, I can use default parameters but it isn't the case with C. Although I can use something like -

int fibo(int n){return fiboN(n - 1, 0, 1);}
int fiboN(int n, int a, int b){return (n>0)? fiboN(n-1, b, a+b) : a;}

But will it be enough to abstract the whole idea? How should I convince others that the approach isn't wrong (although bit vague)?

(I know, this isn't sort of question that I should I ask on SOF but I just wanted to get advice from experts here.)

Answer 1

With the understanding that the base case in your recursion should be a rather than 0, this seems to me to be an excellent (although not optimal) solution. The recursion in that function is tail-recursion, so a good compiler will be able to avoid stack growth making the function O(1) soace and O(n) time (ignoring the rapid growth in the size of the numbers).

Your professor is correct that the caller should not have to deal with the correct initialisation. So you should provide an external wrapper which avoids the need to fill in the values.

int fibo(int n, int a, int b) {
    return n > 0 ? fibo(b, a + b) : a;
}
int fib(int n) { return fibo(n, 0, 1); }

However, it could also be useful to provide and document the more general interface, in case the caller actually wants to vary the initial values.

By the way, there is a faster computation technique, based on the recurrence

fib(a + b - 1) = f(a)f(b) + f(a - 1)f(b - 1)

Replacing b with b + 1 yields:

fib(a + b) = f(a)f(b + 1) + f(a - 1)f(b)

Together, those formulas let us compute:

fib(2n - 1) = fib(n + n - 1)
            = fib(n)² + fib(n - 1)²

fib(2n)     = fib(n + n)
            = fib(n)fib(n + 1) + fib(n - 1)fib(n)
            = fib(n)² + 2fib(n)fib(n - 1)

This allows the computation to be performed in O(log n) steps, with each step producing two consecutive values.