I was going on a walk the other night with my wife, and I think she noticed my far off expression and silence. She asked me what I was so thoughtful about, and I admitted my brain was a bit stuck on solving a complex algorithm involving recursion. At that point she asked me what recursion was, she’s very smart, just not a programmer. So I figured there must be some way I could explain recursion without referring to code, syntax, functions, etc.
Here’s the little explanation I came up with on a moments notice:
Let’s say we have a guy named Joe. Joe has some problems and special abilities.
Joe has the neat ability to make temporary clones of himself, when they’re done doing what he asks them, they disappear in a puff of smoke. Joe unfortunately has issues with math. If you hand him a basket of apple’s, he couldn’t tell you how many apples are in the basket, just seeing all those apples at once confuses him.
If you tell Joe a number though, he can easily add 1 to it. So you tell Joe, “Hey, if someone gives you a basket of apples, take one out, clone yourself, and hand the basket to your clone. If the basket is empty after taking the apple out, tell the one that created you there’s 1. When you get a number from the clone you made, add 1 to it, and tell that to the clone that created you.”
Since Joe’s clones know what he knows, they all know these directions as soon as Joe clones himself. So you proceed to hand a basket of 3 apples to Joe.
Joe takes one out, and hands the basket of 2 apples to his clone. Clone 1 takes an apple out, and handes the basket of 1 apple to a new Clone (Clone 2). Clone 2 takes out the apple, sees there’s no more left, and tells Clone 1, “Hey, there’s 1”. Clone 1 adds 1 to it, and tells Joe, “Hey, there’s 2”.
Joe adds 1 to this, and tells you, the basket has 3 apples in it.
You can hand Joe a basket of however many doodad’s as you want, and he’ll happily keep cloning himself until sooner or later a clone takes out the last doodad.
After this little story, you should be able to explain that:
- A Terminating Condition is when Joe should stop cloning himself
- Joe is recursive because he clones himself and repeats the task
If anyone else out there has a more elegant or shorter way to explain recursion to a non-programmer, I’d love to hear it. This story could also set you up to explain such fun concepts as tail-end recursion or the difference between truly recursive functions and one that could be easily re-written in a loop. I’ll leave that to someone else to translate to non-computer speak.