Рекурсия — это когда функция вызывает сама себя, чтобы решить задачу по частям.
АЛГОРИТМ составь_числа(текущее, сколько_осталось)
// Базовый случай: все цифры выбраны
ЕСЛИ сколько_осталось = 0 ТО
ВЫВЕСТИ текущее
ВЫЙТИ ИЗ ФУНКЦИИ
КОНЕЦ ЕСЛИ
// Перебираем все возможные цифры
ДЛЯ КАЖДОЙ цифры ИЗ [1, 2, 3] ВЫПОЛНЯТЬ
// Создаём новую строку, добавив цифру
новое ← текущее + цифра
// Рекурсивно вызываем для оставшихся позиций
составь_числа(новое, сколько_осталось - 1)
// Сюда вернёмся, когда рекурсия закончится
// Цикл продолжится со следующей цифры
КОНЕЦ ЦИКЛА
КОНЕЦ АЛГОРИТМА
// Запуск
составь_числа("", 3)
Как это работает
Визуальная схема (дерево вызовов)
составь_числа("", 3)
├── цифра=1 → составь_числа("1", 2)
│ ├── цифра=1 → составь_числа("11", 1)
│ │ ├── цифра=1 → составь_числа("111", 0) → ВЫВОД "111"
│ │ ├── цифра=2 → составь_числа("112", 0) → ВЫВОД "112"
│ │ └── цифра=3 → составь_числа("113", 0) → ВЫВОД "113"
│ ├── цифра=2 → составь_числа("12", 1)
│ │ ├── цифра=1 → ВЫВОД "121"
│ │ ├── цифра=2 → ВЫВОД "122"
│ │ └── цифра=3 → ВЫВОД "123"
│ └── цифра=3 → составь_числа("13", 1)
│ ├── ... → "131", "132", "133"
├── цифра=2 → составь_числа("2", 2)
│ └── ... → "211", "212", ..., "233"
└── цифра=3 → составь_числа("3", 2)
└── ... → "311", "312", ..., "333"
Аналогия: развилки в лабиринте
Ты стоишь на развилке с 3 путями (цифры 1, 2, 3).
1. Идёшь по пути "1"
2. Встречаешь новую развилку — опять 3 пути
3. Идёшь по пути "1" → ещё развилка
4. Идёшь по пути "1" → тупик! Записываешь "111"
5. ВОЗВРАЩАЕШЬСЯ на шаг назад
6. Пробуешь путь "2" → тупик! Записываешь "112"
7. ВОЗВРАЩАЕШЬСЯ, пробуешь "3" → "113"
8. Все пути проверены → ВОЗВРАЩАЕШЬСЯ ещё на шаг назад
9. Пробуешь путь "2" с той развилки..