Recursion: Not that hard

In July, I taught Java to about 30 high school students who had little or no prior programming experience. The curriculum was largely set for me, so I won't comment on the choice of language or lots of other things that I might be opinionated about.

In the course of teaching the students about methods, fairly early in their experience, I gave them the challenge of figuring out how to right a program that would print out the first several numbers in the fibonacci sequence. First we worked through the algorithm of how to find out a given fibonacci number: I wrote up a sequence and challenged them to figure out the formula:

n	fib(n)
0	0
1	1
2	1
3	2
4	3
5	5
n	???

After a few false starts, they figured out that fib(n) = fib(n-1) + fib(n-2) except for fib(0) = 0 and fib(1) = 1. 

Now, to be completely honest, I had forgotten that there's an iterative way to solve fibonacci, because the recursive way is SO OBVIOUS. 

So I told them that another thing about methods, in addition to them being able to take parameters and return values, is that they can call themselves. And thus, they wrote recursive algorithms, without pain or suffering:

if (n=0) {return 0;}

else if (n=1) {return 1;}

else {return (fib(n-1) + fib(n-2));}

And some undergraduates who observed it expressed great concern because recursion is a topic they cover in data structures and therefore obviously complex and advanced and presumably inappropriate for my poor little inexperienced high schoolers. Who, I must say, did not appear confused or scarred in any way from the experience.

Clearly there's lots more about recursion I didn't cover, not the least of which is why this is a pretty inefficient solution. But this experience - where recursion was the obvious solution to a problem and there was a straightforward way to handle it - seemed like a nice little introduction to the idea that a method can call itself. No need for awe and fear. And I wonder, if we just introduced recursion as the obvious solution to a few easy problems and handled the more complicated pieces later when students are more prepared, would it go better? 

I think next time, after I gave the students a day or two to adjust to writing methods, control structures, parameters and return values, I'd return to the idea of efficiency and why some solutions are more efficient than others in different ways.