Hi everyone!

Over the last few days, I focused almost entirely on recursion. Before that, I could sometimes write a recursive function by following a familiar pattern, but I did not always understand why it worked or how to discover the recursive idea in a new problem.

Now I have started approaching these problems differently. Instead of writing code immediately or trying to imagine every function call, I first define the meaning of the state.

What I now do before writing recursion

Before coding, I try to answer four questions:

• what exactly the function should do or return;
• what the simplest possible case is;
• how the answer can be expressed using a smaller problem;
• why every recursive call moves closer to termination.

For example, if a function solves a problem for $$$n$$$, the next call usually works with a smaller value such as $$$n-1$$$, $$$n/2$$$, or another simpler state.

The most important thing is that recursion must not call itself forever. That is why every recursive function needs a base case.

A simple example:

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

The function solves the problem for $$$n$$$ using the smaller problem for $$$n-1$$$.

The recurrence is:

The base case is:

Before, I mostly memorized code like this. Now I understand the purpose of every part much better.

Branching recursion

I also understood the difference between a single chain of recursive calls and a situation where one state creates several new states.

A good example is the binomial coefficient recurrence:

The base cases are:

• $$$k=0$$$;
• $$$k=n$$$.

In both cases, the answer is $$$1$$$.

def combinations(n, k):
    if k == 0 or k == n:
        return 1
    return combinations(n - 1, k - 1) + combinations(n - 1, k)

Here, one call creates two more calls, so the number of computations grows very quickly.

This helped me understand that a correct recurrence does not automatically mean an efficient solution.

Memoization and repeated states

Some of my recursive solutions received TLE, even though the main idea was correct.

The problem was that the program calculated the same state many times.

For example, while computing binomial coefficients, the same pair of values n and k can appear again and again.

Memoization solves this problem:

from functools import cache

@cache
def combinations(n, k):
    if k == 0 or k == n:
        return 1
    return combinations(n - 1, k - 1) + combinations(n - 1, k)

Now the result of every state is stored.

When the function is called again with the same arguments, Python returns the saved result instead of calculating everything again.

After learning this, I started asking myself an important question:

Am I solving the same small problem more than once?

If the answer is yes, memoization or dynamic programming may be needed.

Tower of Hanoi

For a long time, I could not properly understand the Tower of Hanoi problem.

The code is short, but the recursive transition initially felt almost magical.

A visual explanation on YouTube finally helped me see the three main steps:

1. move $$$n-1$$$ disks from the starting rod to the auxiliary rod;
2. move the largest disk to the destination rod;
3. move the $$$n-1$$$ disks from the auxiliary rod to the destination rod.

So the problem for $$$n$$$ disks is reduced to two problems for $$$n-1$$$ disks.

The number of moves satisfies:

The final number of moves is:

Once I understood these three steps, the code became much clearer:

def hanoi(n, start, finish, auxiliary):
    if n == 1:
        print(start, finish)
        return

    hanoi(n - 1, start, auxiliary, finish)
    print(start, finish)
    hanoi(n - 1, auxiliary, finish, start)

My main lesson was that one good visualization can sometimes teach more than repeatedly reading finished code.

My first real understanding of DFS

After basic recursion, I started learning graph traversal.

One of the problems involved a room or maze represented by a grid.

At first, I only saw it as a two-dimensional array. Then I found a more useful model:

• every available cell is a graph vertex;
• moving to a neighboring cell is an edge;
• the entire reachable area is a connected component.

A DFS function works approximately like this:

1. check whether the cell is valid;
2. mark it as visited;
3. recursively visit neighboring cells.

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return 0

    if grid[x][y] == '#':
        return 0

    if visited[x][y]:
        return 0

    visited[x][y] = True

    result = 1
    result += dfs(x + 1, y)
    result += dfs(x - 1, y)
    result += dfs(x, y + 1)
    result += dfs(x, y - 1)

    return result

The idea can be written as:

where $$$u$$$ represents the unvisited neighbors of vertex $$$v$$$.

Why visited cells must be marked

Previously, I did not fully understand why the visited array was so important.

Now I see two clear reasons.

First, without visited marks, the algorithm can move in a cycle:

A -> B -> A -> B -> ...

Second, the same cell may be counted several times.

That is why a vertex should be marked as visited immediately after entering it, not after processing all of its neighbors.

This is a small implementation detail, but without it DFS may produce a wrong answer or never terminate.

Trees and choosing the right representation

I also solved a problem where a message had to be deleted together with all of its replies.

The input was naturally represented as:

message -> parent

However, this representation is inconvenient when we need to find every descendant.

A better structure is:

parent -> list of children

For example:

children = [[] for _ in range(n)]

for child, parent in relations:
    children[parent].append(child)

After that, deleting every reply becomes a normal subtree traversal:

def remove_subtree(v):
    removed[v] = True

    for child in children[v]:
        remove_subtree(child)

This helped me understand an important principle:

Sometimes the main difficulty is not the algorithm itself, but the way the input data is represented.

With the correct representation, the final solution can become very short.

Mistakes I fixed

During these days, I noticed several mistakes that appeared repeatedly in my code.

1. Printing instead of returning a value

Sometimes I wrote a recursive function that immediately printed something, even though I later needed its result in another calculation.

Now I try to separate:

• calculating the result with return;
• displaying the result with print.

For example:

def sum_digits(n):
    if n == 0:
        return 0
    return n % 10 + sum_digits(n // 10)

print(sum_digits(12345))

2. Unnecessary global variables

Global variables can make a solution harder to understand and debug.

Now I try to pass the necessary data through function arguments or return the result from the function.

3. Choosing the wrong data structure

When fast membership checks are needed, set is usually better.

used = set()

if value in used:
    ...

On average, a set membership check works in $$$O(1)$$$, while searching in a list takes $$$O(n)$$$.

4. Trying to modify a string

I also reinforced the fact that Python strings are immutable.

This does not work:

s[0] = 'a'

Instead, we need to create a new string or convert it into a list first:

s = list(s)
s[0] = 'a'
s = ''.join(s)

5. Writing code too early

Sometimes I started implementing a solution before deciding:

• what the vertices are;
• which transitions are possible;
• what the function stores or returns;
• which states have already been visited.

Now I try to build the model first and write the implementation only after that.

Practical advice for other beginners

Here are a few things that really helped me understand recursion better.

Define the meaning of the function first

Do not start with the first line of code.

First, describe the function in words:

dfs(v) returns the size of the area reachable from vertex v.

Or:

solve(n) returns the answer for a problem of size n.

After that, the base case and transition usually become much easier to find.

Do not try to hold the entire recursion tree in your head

A recursive function only needs to correctly solve the current problem while assuming that the smaller problem is already solved correctly.

This is much easier than manually imagining hundreds of calls.

Check that the problem becomes smaller

Every recursive call must move closer to the base case.

For example:

solve(n - 1)

is usually safer than:

solve(n)

The second version may create infinite recursion.

Draw small examples

For $$$n=3$$$ or for a small grid, drawing the recursion tree on paper is very useful.

It helps reveal:

• repeated states;
• the order of calls;
• when the function returns;
• why visited is needed.

Always estimate complexity

Even correct recursion may be too slow.

If every state creates two new calls, the complexity may be close to $$$O(2^n)$$$.

If every state is stored and calculated only once, the solution may improve to $$$O(n)$$$ or $$$O(nk)$$$.

What I want to study next

Over the next few days, I want to practice:

• DFS on graphs;
• DFS on two-dimensional grids;
• connected components;
• tree traversal;
• BFS and queues;
• first dynamic programming problems.

I especially want to become faster at identifying the correct problem model before writing code:

• array;
• graph;
• tree;
• grid;
• dynamic programming state.

My main conclusion from these three days is:

Recursion becomes much easier when you stop treating it like magic and start understanding the exact meaning of every call, the base case, and the transition to a smaller problem.