Search code examples
crecursionfibonacci

Fibonacci using Recursion


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.)


Solution

  • Although @rici 's answer is mostly satisfactory but I just wanted to share what I learnt solving this problem. So here's my understanding on finding fibonacci using recursion-

    • The traditional implementation fibo(n) { return (n < 2) n : fibo(n-1) + fibo(n-2);} is a lot inefficient in terms of time and space requirements both. This unnecessarily builds stack. It requires O(n) Stack space and O(rn) time, where r = (√5 + 1)/2.
    • With memoization technique as suggested in @Simion 's answer, we just create a permanent stack instead of dynamic stack created by compiler at run time. So memory requirement remains same but time complexity reduces in amortized way. But is not helpful if we require to use it only the once.
    • The Approach I suggested in my question requires O(1) space and O(n) time. Time requirement can also be reduced here using same memoization technique in amortized way.
    • From @rici 's post, fib(2n) = fib(n)² + 2fib(n)fib(n - 1), as he suggests the time complexity reduces to O(log n) and I suppose, the stack growth is still O(n).

    So my conclusion is, if I did proper research, time complexity and space requirement both cannot be reduced simultaneously using recursion computation. To achieve both, the alternatives could be using iteration, Matrix exponentiation or fast doubling.