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