Recursion is when a process refers back to itself to solve a puzzle. It is like seeing your reflection in a mirror that is looking into another mirror.

The Mirror Effect

Recursion works by taking a big task and turning it into a slightly smaller version of the same thing. You keep doing this until the task becomes simple enough to solve instantly.

Smaller Task Versions

Think of a set of dolls where each one holds a smaller version of itself inside. To get to the tiniest doll, you must open every larger one first.

Russian Nesting Dolls

Imagine asking the person in front of you what row they are in so you can find your own row. That person then asks the person in front of them, passing the question along until someone reaches the very front.

The Movie Theater Puzzle

The computer uses a mental list called a 'stack' to remember where it left off in each step. Each time a task calls itself, a new reminder is placed on top of this pile.

The To-Do Stack

Once the smallest task is finished, the computer goes back through its stack of reminders to complete the bigger tasks. This is like following a breadcrumb trail back to the starting point.

Climbing Back Down

If you forget to include a stop rule, the process will repeat endlessly. This usually causes the computer to run out of memory and crash because the 'to-do stack' becomes too tall.

Infinite Repeating Trap

Imagine looking for a file inside many layers of folders and sub-folders. You look in one folder, and if there are more folders inside, you repeat the same search process there.

Searching Through Folders

Recursion is often used to calculate sequences where each number depends on the one before it. It builds a chain of results that eventually lead to the final answer.

The Math Chain

This technique breaks a difficult problem into two or more smaller, identical problems. By solving the tiny pieces first, you eventually solve the entire big picture.

Dividing to Conquer

Some problems grow like branches on a tree, splitting into multiple paths at once. Recursion helps by following each individual branch until it reaches the very end.

The Branching Tree

Each time a task repeats, it takes up a little bit of the computer's memory. Designers must be careful not to make the recursion too deep, or the computer will run out of room.

Memory Space Warning

While simple loops repeat a task in a straight line, recursion is better for 'nested' problems. It is the best choice when a problem naturally contains smaller copies of itself inside.

The Quest for a File