## Wednesday, December 8, 2010

### A Kid-Friendly Analogy for Recursion

A kid I had taught last year came by after school the other day for some help with the concept of recursion. After a few minutes of looking at some simple examples, she still was kind of confused about why some values would depend on other values, where as some values (ie. the base case) don't need other values in order to be computed. I tried explaining it using the simple examples in the textbook and by looking at the recursive formula of the Fibonacci sequence. Still, she only half-understood, so I decided to throw out an off-the-wall analogy:
Let's say I tell you and a bunch of other kids to make a straight line, facing forward. Then, I tell every kid to smack the head of the kid in front of them. So, you smack the head of some kid, he smacks the head of another kid, etc. Until we get to the front. The kid in the very front, what does he do? He can't do anything; he doesn't have someone in front of him to smack. That sucker's sort of like the base case. The base case is the value you're given at the beginning of the problem because that's the one that you can't calculate.

The funny thing is, the kid totally got the crazy analogy! She said, "So basically, every number in the sequence depends on the one that comes before it, except for the base case. That's the number at the beginning, so it doesn't have any other numbers in front of it in order for you to calculate it, and so its value needs to be given to you by the problem." And then she proceeded to ask me smart questions like what happens if you're trying to calculate the 103rd element -- are you going to need to find all 102 elements before it? (And we got into a pretty good discussion about tradeoffs between different formula types.) ...I guess the moral of the story is that I should make kids smack each other more often in class, for the sole purpose of improving their grasp of confusing mathematical concepts. ;)