If you ask a typical computer science graduate from Kerala to write a program to print the nth Fibonacci number, most of them* will invariably give you the following function:
int fibonacci (int n){
if(n<2){
return n;
}else{
return fibonacci(n-1) + fibonacci(n-2);
}
}
So far so good, except that the answer is wrong.
Recursion is the worst way to find a Fibonacci number. The last time I checked it was impossible to use recursion to compute even the 50th Fibonacci number in a personal computer!
If it is impossible to calculate even the 50th Fibonacci number using this function, how could you possibly teach something like this in a computer science course? The only way Fibonacci numbers should be calculated is by linearly adding the numbers in a loop or by using any direct formula you have. Of course for some applications you can speed up recursion by remembering the child nodes in the tree and thereby avoiding doing the same calculations again in some other branch.
The scariest part is yet to come. In many colleges they use finding the nth Fibonacci number as the primary example for teaching recursion!
Why not teach students the best possible way to find the nth Fibonacci number? Why not teach a real world example for recursion? Is it necessary to teach the concepts in computer science using lousy examples?
*Take blanket statements with a grain of salt.
Well said. I don’t remember how I was taught recursion – but I guess it was factorials. Even though it can be done with a simple loop, factorial is a good example to introduce recursion to a student I believe.
Btw, reached here from SO – where is the upvote button?
Even though I agree that recursion is not the right way to find a Fibonacci number, I have to say using it to teach recursion is a good idea. Because its simple. Easy to get the concept thru this example.
The most common real world application for recursion is to walk thru a tree structure. That example will be complicated. Also you will have to have an understanding of trees and stuff before hand.
Then again, there may be a simple, but real world example that I’m not yet aware of. If someone knows of one, let me know.
Binny,
As Amarghosh pointed out, factorial is a good example.
Another very simple example is addition:
add(0, x) = x,add(n, x) = add(n-1, x) + 1
As far as I know this example is often used in computer science courses in many good universities around the world.
I think Fibonacci should be taught as an example for bad use of recursion. Of course the point is that there is a huge time-space trade-off in using recursion and that should be taught correctly.
First thing : stop thinking that those who make syllabus/curriculum are fools or outdated, they know more than you in programming(i refer to those who make syllabus and curriculum not your lecturer at coll)
Second thing : Before appreciating think not even once, but before criticizing think a thousand times.
Third thing : Search Google, Refer Wikipedia and then post what you feel ,ie. when you do tech blog.
Fourth point : Fibonacci is inherently recursive, find what is recursion in mathematics, recurrence relations and recursive functions.
Fifth point : I have made all of the above mentioned mistakes myself. Keep rocking dude!!
sabithpocker,
Even though the definition of Fibonacci is recursive, it does not mean that you can compute Fibonacci numbers using recursion.
While the best algorithm for the generation of the fibonacci sequence is not a recursive algorithm, the fibonacci sequence is still a very useful example of explaining recursion. For people who are seeing recursion for the first time, it’s something very easy to visualize and has a low enough number of recursive calls as to make drawing the recursion tree feasible.
The way I’ve seen it taught in various places normally will use the fibonacci sequence as a segue into dynamic programming and memoization. Because the recursive algorithm is so terrible, it makes an excellent example of how performance can be drastically improved by preventing duplicate calls.
Factorial and addition do not lend themselves to such a segue, and are therefore less commonly used. Also, when doing introductory programming courses – doing factorial will be limited far sooner by the capacity of integers than it will be by computational complexity.
We are not trying to ‘calculate’ Fibonacci numbers using computer.. are we?
We are instead studying a concept called ‘recursion’.