Recursion Tower — Recursion

How to play

Write the recursive function and press Run. Underneath, every call your function actually made is drawn in order: indented by how deep it was, with the arguments going in and the value coming back out. That picture is the entire point of this game. Recursion is hard to learn from prose because the interesting part — the stack building up and then unwinding — is invisible.

Loops are blocked on most levels, so recursion is the only way through.

What each level teaches

1. Add them up — base case and recursive case, the two halves every recursion needs.
2. Factorial — work that happens on the way back, as the stack unwinds.
3. Backwards — recursion on a string: do one character, hand the rest on.
4. Down and back up — printing before and after the recursive call, which makes the unwinding audible.
5. Fibonacci — two recursive calls, and the explosion in call count that follows.
6. All the way down — recursion over nested data, where it genuinely beats a loop.

The two halves of every recursive function

• A base case that returns without calling again. Without it you get RecursionError after about a thousand calls.
• A recursive case that does one small piece of work and calls itself on something smaller. If the argument does not shrink towards the base case, the base case never arrives.

Nearly every broken recursion is one of those two: no base case, or an argument that is not getting closer to it.

Watch what level 5 costs

Run fib(5) and count the frames: fifteen calls for a number you could work out on your fingers. The reason is that each call spawns two more, and the same values are computed again and again — fib(2) alone is calculated several times. Push it to fib(30) and you are into millions of calls. This is the classic demonstration that a correct recursion can still be a bad algorithm, and why functools.lru_cache exists, which the standard library lesson covers.

When recursion is the right tool

Honestly: less often than tutorials imply. Counting down, summing a range and reversing a string are all clearer and faster as loops — they appear here because they make the stack easy to see, not because you should write them this way. Recursion earns its place when the data is shaped like itself: nested lists, JSON, a folder tree, an HTML document. That is level 6, and it is the only one where a loop alone will not do the job.

The written explanation sits in the Python functions tutorial.

Practise recursion on your phone — the Coding Python app runs real Python 3 on your phone, with examples, quizzes and challenges built in.

Get it free

Frequently asked questions

Keep going

• Read the recursion tutorial — the written explanation behind every level here.
• Variable Vault — variables & data types.
• Operator Arcade — numbers & operators.
• String Surgeon — strings & slicing.
• 20 Python practice exercises with worked solutions.

← All Python coding games  Read the tutorial →