An Explanation of Recursion Like You're Five

Or: ReyCursion is a Snap

This post was adapted from my comment on Explain Recursion Like I'm Five

Let's say you want to add up a bunch of numbers. You have the numbers on a stack of index cards, one number on each card. Somebody asked you to add them up and tell them the result. That sounds like a lot of work. I mean, come on, adding a couple numbers is fine, but there are probably like 50 numbers in this deck of cards. So you hatch a plan...

You keep the top card, and you hand the rest to your classmate and ask them to add up rest of the cards. You don't tell them that this was supposed to be your job.

Your classmate says fine, but then realizes there must be like 49 cards in this deck, which sounds like a lot, I mean come on? So they hatch a plan. They keep one card for themselves and ask somebody else to add up the rest of the cards...

And so on down the line (fortunately your school is pretty overcrowded and you have a lot of classmates) until somebody is handed just one card and asked to add "them" up.

"What do you mean add 'them' up, it's just one card."

"But what do they add up to?"

Okay whatever, so the last person just says the number on the card.

The second-to-last person takes that number and adds it to the card they kept, and tells it to the person who asked them.

The third-to-last person takes the number that the second-to-last person tells them and adds it to the number on the card they kept, and so on back up the line....

You get the number that the second person tells you and add it to the one card you kept. Easy peasy lemon squeezy! Then you tell the person who asked you.

In code, this would look something like:

def sumof(deck):
    if len(deck) == 1:
        return deck[0]
    else:
        mycard = deck.pop()
        return mycard + sumof(deck)

One problem is that this destroys the deck. We could have each person give the card back when they say the result (deck.push(mycard)), but in code it's cleaner to just pass a slice of the rest of the deck:

def sumof(deck):
    if not deck:
        return 0
    else:
        return deck[0] + sumof(deck[1:])

Comments

[Luke Bayliss]

Brilliant explanation. This would be perfect for a class demonstration of how recursion works.

[Dani J. Pérez]

Very good explanation! :D

Good work!