Logout

# Recursion Analogies

(Refer also to "Stacking Analogies".)

### Recursion Analogy 1 - "George"

You ask me who took the nice picture, and I say "George". But you don't know who George is, so you ask me a question:

"Who_is (George)?"

But with this information, you still don't know who George is because you don't know who Alexander is. So you have to break down the problem further ("divide and conquer principle"), and ask another instance of the same sort of question ("self-same principle").

"Yeah, but who_is (Alexander)?"

"He's Elizabeth's father."

Hmmm... still no satisfaction...

"Sure, but who_is (Elizabeth)?"

"Oh, that's actually Liz's real name."

You still don't know how to put who the picture taker is in context, but you sure hope you're getting closer...

"Well, who_is (Liz)?"

"Liz is Billy Smith's mother."

"Ah ha!, I know Billy Smith" (So now you can work your way back down through the stack:

Billy Smith's mother,
who is named Liz,
who is also named Elizabeth,
has a father whose name is Alexander,
who has a brother named George.

That's who George is:

George is Billy Smith's mother's father's brother; i.e. Billy Smith's great uncle.

The recursive method is asking who_is a certain person, but each time you call the method you are sending a different argument. And fortunately there is a base case which is a person that you know, so all the questions are answered (in LIFO fashion), all the methods thus completed.

### Recursion Analogy 2 - "Antananarivo"

Wow, you're a really good programmer. At some point I'd like to come over and do some recursive programming with you. So tell me, where do you live?

On Rue Andriantsihoarana?                 (This doensn't help, so have to put that where_is on a stack of undone where_is methods and call another where_is method)

Ok, where_is(Rue_Andriantsihoarana)

It's in Analamahitsy.                                             (ditto)

Sure, but where_is(Analamahitsy)?

It's in Antananarivo.                                                (ditto)

Fine. That rings a bell... where_is(Antananarivo)?

It's the capital city of Madagascar.                               (ditto)

It's the big island country off the east coast of Africa.

A ha! So now if I go to Madagascar,
and then to Antananarivo,
and then to Analamahitsy,
and then to Rue Rainizanabololona,
I will find you!

### Recursion Analogy 3 - "The Little Old Lady"

How come that little old lady over there swalled a horse and is now dead of course?

So, why_did_she_swallow_the(horse)?

She swallowed the horse to eat the dog.

Yeah, but why_did_she_swallow_the(dog)?

She swallowed the dog to eat the cat.

Sure, but why_did_she_swallow_the(cat)?

She swallowed the cat to eat the bird.

Ok, but why_did_she_swallow_the(bird)?

She swallowed the bird to eat the spider.

Fine, but why_did_she_swallow_the(spider)?

She swallowed the spider to eat the fly.

Ok, but why_did_she_swallow_the(fly)?

Because it's just one of those things; sometimes a little old lady has a fly fly into her mouth by accident, and she swallows it.

A ha! So she swallowed the horse to eat the dog,
she swallowed the dog to eat the cat;
she swallowed the cat to eat the bird;
she swallowed the bird to eat the spider;
she swallowed the spider to eat the fly
that flew into her mouth from out in the sky.

And now I know why she swalled the horse.... of course!!

### Other Recursion Analogy Examples:

- The way that when you start to organize part of your bedroom, the next thing you know you are pulling the room all apart and putting it back together again. The recursive pattern is organize_this( ) and in the middle of that "method" another call to organize_this( ) with a different parameter. And once you get to the base case of the last thing that needs to be pulled out and organized, you can go down through the stack of things waiting to be dealt with until you get to the one that you started with.

- Me making my teaching easier through an initial call to add_website_feature( ), but in the middle of doing so seeing that I need to do another add_website_feature( ) with a different parameter, and so on and so on, calling new instance recursively. But everntually the later calls to add_website_featuer( ) finish, and thereby alllow the former calls, one at a time, to also be finished. And at the end (some time in 2016??) everything works perfectly...