↵
Последние несколько дней я почти полностью посвятил **рекурсии**. До этого я мог написать рекурсивную функцию по знакомому шаблону, но не всегда понимал, *почему* она работает и как самостоятельно увидеть рекурсивную идею в новой задаче.↵
↵
Сейчас я начал смотреть на такие задачи немного иначе. Вместо того чтобы сразу писать код или пытаться представить все вызовы функции, я сначала разбираю смысл состояния.↵
↵
## Что я начал делать перед написанием рекурсии↵
↵
Теперь перед кодом я стараюсь ответить на четыре вопроса:↵
↵
* что именно должна делать или возвращать функция;↵
* какой случай является самым простым;↵
* как получить ответ через задачу меньшего размера;↵
* почему каждый новый вызов приближает нас к остановке.↵
↵
Например, если функция решает задачу для числа $n$, то следующий вызов обычно должен работать с меньшим значением: $n-1$, $n/2$ или другой более простой версией состояния.↵
↵
Самое важное — рекурсия не должна вызывать сама себя бесконечно. Поэтому нужен **базовый случай**.↵
↵
Простой пример
↵
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:↵
↵
```python↵
def factorial(n):↵
if n == 0:↵
return 1↵
return n * factorial(n - 1)↵
```↵
↵
↵
Формула выглядит так
↵
The recurrence is:↵
↵
$$↵
n! = n \cdot (n-1)!↵
$$↵
↵
↵
$$↵
0! = 1↵
$$↵
↵
↵
## Ветвящаяся рекурсия↵
↵
Ещё я понял разницу между обычной цепочкой рекурсивных вызовов и ситуацией, когда из одного состояния появляются сразу несколько следующих состояний.↵
↵
Хороший пример — биномиальные коэффициенты.↵
↵
Для них используется формула
↵
## 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:↵
↵
$$↵
C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}↵
$$↵
↵
↵
* $k=0$;↵
* $k=n$.↵
↵
↵
```python↵
def combinations(n, k):↵
if k == 0 or k == n:↵
return 1↵
return combinations(n - 1, k - 1) + combinations(n - 1, k)↵
```↵
↵
↵
Именно на таких задачах я начал лучше понимать, почему правильная формула ещё не гарантирует быстрое решение.↵
↵
## Мемоизация и повторяющиеся состояния↵
↵
Некоторые рекурсивные решения у меня получали **TLE**, хотя сама идея была правильной.↵
↵
Проблема оказалась в том, что программа много раз вычисляла одно и то же состояние.↵
↵
Например, при вычислении биномиальных коэффициентов вызов с одинаковыми значениями `n` и `k` может появляться снова и снова.↵
↵
Для таких случаев можно использовать мемоизацию:↵
↵
```python↵
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)↵
```↵
↵
Теперь результат каждого состояния сохраняется.↵
↵
Если функция снова вызывается с теми же аргументами, Python не вычисляет всё заново, а берёт готовый ответ.↵
↵
После этого я начал задавать себе полезный вопрос:↵
↵
> Не решаю ли я одну и ту же маленькую задачу несколько раз?↵
↵
Если ответ положительный, то, скорее всего, нужна мемоизация или динамическое программирование.↵
↵
## Ханойские башни↵
↵
Долгое время я не мог нормально понять задачу о Ханойских башнях.↵
↵
Сам код выглядит коротко, но рекурсивный переход сначала казался почти магическим.↵
↵
Мне помогло визуальное объяснение на YouTube. После него я наконец увидел три основных шага:↵
↵
1. перенести $n-1$ дисков с начального стержня на вспомогательный;↵
2. перенести самый большой диск на конечный стержень;↵
3. перенести $n-1$ дисков со вспомогательного стержня на конечный.↵
↵
То есть задача для $n$ дисков сводится к двум задачам для $n-1$ дисков.↵
↵
Количество действий задаётся рекуррентной формулой:↵
↵
$$↵
T(n)=2T(n-1)+1↵
$$↵
↵
Итоговое количество перемещений:↵
↵
$$↵
T(n)=2^n-1↵
$$↵
↵
После того как я понял именно эти три шага, код уже стал намного понятнее:↵
↵
```python↵
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)↵
```↵
↵
Главный вывод для меня: иногда одна хорошая визуализация даёт больше, чем много попыток просто читать готовый код.↵
↵
## Первое настоящее понимание DFS↵
↵
После обычной рекурсии я начал разбирать обходы графов.↵
↵
Одна из задач была связана с комнатой или лабиринтом, представленным в виде таблицы.↵
↵
Сначала я смотрел на неё просто как на двумерный массив. Потом понял более полезную модель:↵
↵
* каждая доступная клетка — это вершина графа;↵
* переход в соседнюю клетку — это ребро;↵
* вся доступная область — компонент связности.↵
↵
Функция DFS делает примерно следующее:↵
↵
1. проверяет, можно ли зайти в клетку;↵
2. отмечает её как посещённую;↵
3. запускается для соседних клеток
↵
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:↵
↵
```python↵
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:↵
↵
$$↵
T(n)=2T(n-1)+1↵
$$↵
↵
The final number of moves is:↵
↵
$$↵
T(n)=2^n-1↵
$$↵
↵
Once I understood these three steps, the code became much clearer:↵
↵
```python↵
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.↵
↵
```python↵
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↵
```↵
↵
↵
$$↵
dfs(v)=1+\sum dfs(u)↵
$$↵
↵
↵
## Зачем отмечать посещённые клетки↵
↵
Раньше я не до конца понимал, почему массив `visited` настолько важен.↵
↵
Теперь вижу сразу две причины.↵
↵
Во-первых, без отметки посещённых вершин алгоритм может ходить по кругу:↵
↵
```text↵
A -> B -> A -> B -> ...↵
```↵
↵
Во-вторых, одна и та же клетка может быть посчитана несколько раз.↵
↵
Поэтому вершину нужно отмечать посещённой сразу после входа в неё, а не после обхода всех соседей.↵
↵
Это небольшая деталь, но без неё DFS может работать неправильно или вообще не завершиться.↵
↵
## Деревья и правильное хранение данных↵
↵
Ещё мне попалась задача, где нужно было удалить сообщение вместе со всеми ответами на него.↵
↵
Изначально данные было удобно читать в виде:↵
↵
```text↵
сообщение -> родитель↵
```↵
↵
Но для удаления всех потомков это хранение неудобно.↵
↵
Гораздо полезнее построить обратную структуру:↵
↵
```text↵
родитель -> список детей↵
```↵
↵
Например
↵
## 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:↵
↵
```text↵
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:↵
↵
```text↵
message -> parent↵
```↵
↵
However, this representation is inconvenient when we need to find every descendant.↵
↵
A better structure is:↵
↵
```text↵
parent -> list of children↵
```↵
↵
For example:↵
↵
```python↵
children = [[] for _ in range(n)]↵
↵
for child, parent in relations:↵
children[parent].append(child)↵
```↵
↵
↵
```python↵
def remove_subtree(v):↵
removed[v] = True↵
↵
for child in children[v]:↵
remove_subtree(child)↵
```↵
↵
↵
> Иногда главная сложность задачи не в алгоритме, а в том, как представить исходные данные.↵
↵
Если хранение выбрано правильно, само решение может оказаться очень коротким.↵
↵
## Какие ошибки я исправил↵
↵
За эти дни я заметил несколько повторяющихся ошибок в своём коде.↵
↵
### 1. Печать вместо возврата значения↵
↵
Иногда я писал рекурсивную функцию, которая сразу что-то печатала, хотя дальше результат нужно было использовать в вычислениях.↵
↵
Теперь стараюсь разделять:↵
↵
* вычисление результата через `return`;↵
* вывод результата через `print`.↵
↵
Например, лучше так:↵
↵
```python↵
def sum_digits(n):↵
if n == 0:↵
return 0↵
return n % 10 + sum_digits(n // 10)↵
↵
print(sum_digits(12345))↵
```↵
↵
### 2. Лишние глобальные переменные↵
↵
Глобальные переменные могут сделать решение сложнее для понимания и отладки.↵
↵
Теперь стараюсь передавать нужные данные в аргументах функции или возвращать результат.↵
↵
### 3. Неправильный выбор структуры данных↵
↵
Если нужны быстрые проверки принадлежности, лучше использовать `set`.↵
↵
```python↵
used = set()↵
↵
if value in used:↵
...↵
```↵
↵
В среднем проверка через множество работает за $O(1)$, тогда как поиск в списке занимает $O(n)$.↵
↵
### 4. Попытка изменить строку↵
↵
Я ещё раз закрепил, что строки в Python неизменяемые.↵
↵
Так делать нельзя:↵
↵
```python↵
s[0] = 'a'↵
```↵
↵
Нужно создавать новую строку или сначала преобразовывать её в список.↵
↵
```python↵
s = list(s)↵
s[0] = 'a'↵
s = ''.join(s)↵
```↵
↵
### 5. Слишком раннее написание кода↵
↵
Иногда я начинал писать решение, ещё не определив:↵
↵
* что является вершиной;↵
* какие существуют переходы;↵
* что хранит функция;↵
* какие состояния уже посещены.↵
↵
Теперь стараюсь сначала построить модель задачи, а потом переходить к реализации.↵
↵
## Практические советы для других новичков↵
↵
Вот несколько вещей, которые действительно помогли мне лучше понять рекурсию.↵
↵
### Сначала придумайте смысл функции↵
↵
Не начинайте с первой строки кода.↵
↵
Сначала сформулируйте словами:↵
↵
> `dfs(v)` возвращает размер области, достижимой из вершины `v`.↵
↵
Или:↵
↵
> `solve(n)` возвращает ответ для задачи размера `n`.↵
↵
После этого базовый случай и переход становятся намного понятнее.↵
↵
### Не пытайтесь держать в голове всё дерево вызовов↵
↵
Рекурсивная функция должна правильно решать текущую задачу, предполагая, что меньшая задача уже решается правильно.↵
↵
Это намного легче, чем вручную представлять сотни вызовов.↵
↵
### Проверяйте уменьшение задачи↵
↵
Каждый рекурсивный вызов должен приближаться к базовому случаю.↵
↵
Например
↵
> 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:↵
↵
```python↵
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.↵
↵
```python↵
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:↵
↵
```python↵
s[0] = 'a'↵
```↵
↵
Instead, we need to create a new string or convert it into a list first:↵
↵
```python↵
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:↵
↵
```python↵
solve(n - 1)↵
```↵
↵
↵
```python↵
solve(n)↵
```↵
↵
↵
### Рисуйте маленькие примеры↵
↵
Для $n=3$ или маленькой таблицы удобно нарисовать дерево вызовов на бумаге.↵
↵
Это помогает увидеть:↵
↵
* повторяющиеся состояния;↵
* порядок вызовов;↵
* момент возврата из функции;↵
* необходимость `visited`.↵
↵
### Всегда оценивайте сложность↵
↵
Даже правильная рекурсия может быть слишком медленной.↵
↵
Если из каждого состояния появляются два новых вызова, сложность может быть близка к $O(2^n)$.↵
↵
Если все состояния сохраняются и каждое вычисляется один раз, решение часто ускоряется до $O(n)$ или $O(nk)$.↵
↵
## Что дальше↵
↵
В следующие дни хочу закрепить:↵
↵
* DFS на графах;↵
* DFS на двумерных таблицах;↵
* поиск компонент связности;↵
* обход деревьев;↵
* BFS и очередь;↵
* первые задачи на динамическое программирование.↵
↵
Особенно хочу научиться быстрее определять модель задачи ещё до написания кода:↵
↵
* массив;↵
* граф;↵
* дерево;↵
* сетка;↵
* состояние динамического программирования.↵
↵
Главный вывод за эти три дня:↵
↵
> Рекурсия становится намного проще, когда перестаёшь воспринимать её как магию и начинаешь точно понимать смысл каждого вызова, базовый случай и переход к меньшей задаче
↵
### 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.↵
