Do you know Matryoshka dolls?

When you open a doll, you find another doll inside, and when you open that one, there's another one inside. The act of doing this is called recursion. Let's write code for that.

function openDoll(doll) {
    if(doll.isEmpty()) {
        return doll;
    }
    openDoll(doll.open());
}

Recursion is a way of doing an operation over a set of values, where each value is related to the previous one, without iterating or using loops.

Imagine you go to open a room, but the room is locked. You have someone come up to you with a box and they tell you that the key to the room is in there. But inside the box is many other boxes, that also contain boxes and you don't know which box contains the key. So you need an algorithm to find the key!

Imagine you want to pan-fry some fish, but you have a huge fish and not so large a pan. Write down the steps to cut the fish so it fits in the pan.

Fish-Cutting-Steps:

1. If the piece of fish fits in your pan, you're done
2. Otherwise, cut the fish in half
3. Follow "Fish-Cutting-Steps" for each half

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:])

To begin, if you want to understand recursion, you must understand what is recursion.

This explain pretty much the concept of recursion. :D

In the programming world, you can find recursive algorithms, such as sorting ones, and you can guess they aren't looping on themselves infinitely, we always add a return condition to be sure we won't have an infinite loop.

FYI we don't do infinite recursive function because it would pollute the "call stack". This stack keeps track of which function was called, and from where it was called, to be able to get back there when we'll met a return statement.

Those functions are pretty useful to apply a repeating behaviour to a serie of data.

For example :

def bubbleSort(data: list) -> list:
    output = []
    if len(data) > 2:
        middle_element = len(data) // 2
        new_list = bubbleSort(data[:middle_element]) + bubbleSort(data[middle_element:])
        for element in new_list:
            output.append(element)
    else:
        return [min(*data), max(*data)]
    return output

(actually this function isn't working as intended, it was created only to show you the concept of recursion)

Play Tower of Hanoi using stacking rings every toddler probably has in their play bin. That is how I really really understood recursion when I first learned it couple decades ago and it blew my mind :)

• Why can't a plate break a hammer?

  • Because a hammer has a hard head

• But why?

  • Because it's hard.

• But why?

  • Because it's made of hard materials.

• But why?