Understanding recursion: how one of the most mysterious topics in programming works

If you too once looked at a recursive function and felt like you were in an infinite reflection in a mirror — welcome! This article is for you. Today we will break down recursion. Simple, fun, easy to understand and with a bunch of examples. Let's go! 🚀

🔎 What is recursion, in human terms?

Recursion is when a function calls itself (don't panic!). This is necessary to solve the problem by breaking it down into smaller subtasks. This is repeated until we reach the so-called of the base case — breakpoints.

🎭 Imagine an infinite reflection between two mirrors. You, then a little less you, then a microtu — and so on. This is recursion. Only instead of reflections, there are function calls. And each of these calls is a little easier than the previous one, until we get to the one that even a kettle can handle (I mean, a kettle-function!).

📦 Or another example: imagine a box in a box, and in it another box, and so on until you reach the last, smallest one. In programming, this last box is our base case. That's it, there's nothing more to "unpack", it's time to collect the result back.

📌 Example 1: Factorial — recursion favorite

Factorial numbers n (denoted by n!) is the product of all numbers from 1 to n.

Example:

5! = 5 × 4 × 3 × 2 × 1 = 120

Recursive implementation in Python:

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Each call reduces n until we reach 1 or 0, and then the function starts to return the result. It's very similar to going down a slide and coming back up the stairs.

📌 Example 2: sum of numbers up to n

Now let's add all the numbers from 1 to n:

def sum_to(n):
    if n == 1:
        return 1
    else:
        return n + sum_to(n - 1)

Call sum_to(5):

sum_to(5)
= 5 + sum_to(4)
= 5 + (4 + sum_to(3))
= 5 + (4 + (3 + sum_to(2)))
= 5 + (4 + (3 + (2 + sum_to(1))))
= 5 + 4 + 3 + 2 + 1 = 15

Here it is, the magic of recursion: the task "decreases" to an understandable one, and then "adds up" to the answer.

📌 Example 3: countdown (and a useful skill)

def countdown(n):
    if n == 0:
        print("Let's go!")
    else:
        print(n)
        countdown(n - 1)

Launch countdown(5) and you will see:

5
4
3
2
1
Поехали!

Recursion doesn't always have to return values — it can just perform actions. This is a great way to start applying it!

🧨 Mistakes that almost everyone makes (and how to avoid them)

1. ❌ Forgot the base case — and hello to infinite recursion. Check where the function should stop.

2. ❌ Incorrect condition — for example, if n == 0 instead of n <= 0, and you flew away into infinity again.

3. ❌ Recursion where it's easier without it — always ask yourself: "Do I really need recursion here?".

🌟 When recursion really rules

Recursion is convenient when:

• Need to bypass nested structures, such as folders or JSON.

• Task naturally divisible into parts (e.g. sorting, search tree).

• I need to try all paths - ideal for finding solutions in puzzles (maze, sudoku, etc.).

📈 Cons of recursion (don't panic, just be aware of them)

• Each recursive call is an additional memory (call stack).

• Many levels → stack overflows (especially in Python).

• It works slower than normal cycles if not optimized.

✨ How to make friends with recursion forever

1. ✏️ Draw — call tree, stack, sequence of actions.

2. 🎮 Practice — solve problems, even the simplest ones: factorial, sum, line in reverse order.

3. 🔍 Track progress — step by step, with print() or in the debugger.

4. 🧪 Compare with cycles — write both versions to see the pros and cons.

🧪 Example 4: string reversal

def reverse_string(s):
    if len(s) == 0:
        return ""
    return s[-1] + reverse_string(s[:-1])

reverse_string("Code") → "kidoK"

This way you can flip the lines, and it's beautiful and clear.

🎬 Let's summarize

Recursion is:

• a way to break a task down into simple steps;

• a function that calls itself until the base condition is reached;

• magic that can be tamed.

If you still don't fully understand, read the article again. This is also recursion 😉