Подготовка к алгоритмическим задачам

Рекурсия простым языком: как понять и перестать бояться

14 мин чтения

алгоритмы

рекурсия

собеседование

JavaScript

Python

Что такое рекурсия?

Рекурсия — это когда функция вызывает сама себя. Звучит странно? Давайте разберемся.

Простая аналогия: Представьте матрёшку. Чтобы добраться до самой маленькой, вы открываете большую, внутри находите поменьше, открываете её, и так далее, пока не дойдете до последней.

// Самая простая рекурсия
function countdown(n) {
    if (n <= 0) {
        console.log("Готово!");
        return;
    }
    console.log(n);
    countdown(n - 1);  // функция вызывает сама себя
}

countdown(5);
// Выведет: 5, 4, 3, 2, 1, Готово!

Два обязательных компонента рекурсии

Каждая рекурсивная функция должна иметь:

1. Базовый случай (Base Case)

Условие, при котором рекурсия останавливается. Без него функция будет вызывать себя бесконечно.

2. Рекурсивный случай (Recursive Case)

Вызов функцией самой себя с измененными параметрами, приближающими к базовому случаю.

function factorial(n) {
    // Базовый случай — останавливаемся
    if (n <= 1) {
        return 1;
    }

    // Рекурсивный случай — вызываем себя с n-1
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)

# То же на Python
def factorial(n):
    # Базовый случай
    if n <= 1:
        return 1

    # Рекурсивный случай
    return n * factorial(n - 1)

print(factorial(5))  # 120

Как работает рекурсия: стек вызовов

Когда функция вызывает себя, каждый вызов добавляется в стек вызовов. Давайте проследим factorial(4):

factorial(4)
    → 4 * factorial(3)
        → 3 * factorial(2)
            → 2 * factorial(1)
                → 1  (базовый случай!)
            ← 2 * 1 = 2
        ← 3 * 2 = 6
    ← 4 * 6 = 24
← 24

Визуализация стека:

Стек растет вниз:           Стек разворачивается:
┌─────────────────┐         ┌─────────────────┐
│ factorial(4)    │         │ factorial(4)=24 │ ←
├─────────────────┤         ├─────────────────┤
│ factorial(3)    │         │ factorial(3)=6  │ ←
├─────────────────┤         ├─────────────────┤
│ factorial(2)    │         │ factorial(2)=2  │ ←
├─────────────────┤         ├─────────────────┤
│ factorial(1)=1  │ ← стоп  │ factorial(1)=1  │ ← старт
└─────────────────┘         └─────────────────┘

Классические примеры рекурсии

1. Числа Фибоначчи

Каждое число — сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13...

// Простая рекурсия (медленно, но понятно)
function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 55

Проблема: Этот код очень медленный для больших n, потому что одни и те же значения вычисляются многократно.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

2. Сумма массива

function sumArray(arr) {
    // Базовый случай: пустой массив
    if (arr.length === 0) return 0;

    // Рекурсивный случай: первый элемент + сумма остальных
    return arr[0] + sumArray(arr.slice(1));
}

console.log(sumArray([1, 2, 3, 4, 5])); // 15

def sum_array(arr):
    if len(arr) == 0:
        return 0
    return arr[0] + sum_array(arr[1:])

print(sum_array([1, 2, 3, 4, 5]))  # 15

3. Переворот строки

function reverseString(str) {
    if (str.length <= 1) return str;
    return reverseString(str.slice(1)) + str[0];
}

console.log(reverseString("hello")); // "olleh"

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

print(reverse_string("hello"))  # "olleh"

4. Проверка палиндрома

function isPalindrome(str) {
    // Убираем пробелы и приводим к нижнему регистру
    str = str.toLowerCase().replace(/\s/g, '');

    // Базовые случаи
    if (str.length <= 1) return true;

    // Сравниваем первый и последний символы
    if (str[0] !== str[str.length - 1]) return false;

    // Проверяем оставшуюся часть
    return isPalindrome(str.slice(1, -1));
}

console.log(isPalindrome("А роза упала на лапу Азора")); // true

def is_palindrome(s):
    s = s.lower().replace(" ", "")

    if len(s) <= 1:
        return True

    if s[0] != s[-1]:
        return False

    return is_palindrome(s[1:-1])

print(is_palindrome("А роза упала на лапу Азора"))  # True

5. Степень числа

function power(base, exponent) {
    if (exponent === 0) return 1;
    if (exponent < 0) return 1 / power(base, -exponent);
    return base * power(base, exponent - 1);
}

console.log(power(2, 10)); // 1024
console.log(power(2, -2)); // 0.25

def power(base, exponent):
    if exponent == 0:
        return 1
    if exponent < 0:
        return 1 / power(base, -exponent)
    return base * power(base, exponent - 1)

print(power(2, 10))  # 1024

Рекурсия vs Итерация

Любую рекурсию можно переписать через цикл:

// Рекурсия
function factorialRecursive(n) {
    if (n <= 1) return 1;
    return n * factorialRecursive(n - 1);
}

// Итерация (цикл)
function factorialIterative(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Когда использовать рекурсию:

🌳 Работа с деревьями и графами
📁 Обход файловой системы
🧩 Задачи "разделяй и властвуй"
🔄 Когда задача естественно разбивается на подзадачи

Когда использовать итерацию:

➡️ Простые последовательные операции
💾 Когда важна память (рекурсия использует стек)
⚡ Когда критична производительность

Оптимизация рекурсии

Проблема: повторные вычисления

// fibonacci(5) вычисляет fibonacci(2) три раза!
//
//                    fib(5)
//                   /      \
//               fib(4)      fib(3)
//              /    \       /    \
//          fib(3)  fib(2) fib(2) fib(1)
//          /   \
//      fib(2) fib(1)

Решение 1: Мемоизация

Сохраняем уже вычисленные результаты:

function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) return n;

    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

console.log(fibonacciMemo(50)); // 12586269025 (мгновенно!)

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))  # 12586269025

Решение 2: Хвостовая рекурсия

Рекурсивный вызов — последняя операция в функции:

function factorialTail(n, accumulator = 1) {
    if (n <= 1) return accumulator;
    return factorialTail(n - 1, n * accumulator);
}

console.log(factorialTail(5)); // 120

def factorial_tail(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

print(factorial_tail(5))  # 120

Частые ошибки

1. Забыли базовый случай

// ОШИБКА: бесконечная рекурсия!
function badRecursion(n) {
    return n + badRecursion(n - 1);
}
// Вызовет "Maximum call stack size exceeded"

2. Базовый случай недостижим

// ОШИБКА: никогда не достигнем базового случая
function badFactorial(n) {
    if (n === 0) return 1;
    return n * badFactorial(n - 1);
}

badFactorial(-5); // Бесконечная рекурсия!

Исправление:

function goodFactorial(n) {
    if (n <= 0) return 1;  // Обрабатываем и отрицательные числа
    return n * goodFactorial(n - 1);
}

3. Не приближаемся к базовому случаю

// ОШИБКА: параметр не меняется
function stuckRecursion(n) {
    if (n === 0) return 0;
    return 1 + stuckRecursion(n);  // n не уменьшается!
}

Задачи для практики

Задача 1: Сумма цифр числа

function sumDigits(n) {
    n = Math.abs(n);
    if (n < 10) return n;
    return (n % 10) + sumDigits(Math.floor(n / 10));
}

console.log(sumDigits(12345)); // 15 (1+2+3+4+5)

Задача 2: Количество вхождений символа

function countChar(str, char) {
    if (str.length === 0) return 0;
    const count = str[0] === char ? 1 : 0;
    return count + countChar(str.slice(1), char);
}

console.log(countChar("banana", "a")); // 3

Задача 3: Плоский массив из вложенного

function flatten(arr) {
    let result = [];
    for (const item of arr) {
        if (Array.isArray(item)) {
            result = result.concat(flatten(item));
        } else {
            result.push(item);
        }
    }
    return result;
}

console.log(flatten([1, [2, [3, 4], 5], 6])); // [1, 2, 3, 4, 5, 6]

def flatten(arr):
    result = []
    for item in arr:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4], 5], 6]))  # [1, 2, 3, 4, 5, 6]

Советы для собеседования

Определите базовый случай первым — это покажет, что вы понимаете структуру рекурсии
Проверьте граничные случаи — пустой массив, 0, отрицательные числа
Объясните сложность — упомяните O(n) по памяти из-за стека вызовов
Предложите оптимизацию — мемоизация или итеративное решение
Нарисуйте дерево вызовов — это поможет и вам, и интервьюеру

Заключение

Рекурсия — это мощный инструмент, который становится понятным с практикой:

Всегда определяйте базовый случай
Убедитесь, что приближаетесь к нему
Используйте мемоизацию для оптимизации
Практикуйтесь на классических задачах

Как только вы "щелкнете" и поймете рекурсию, многие сложные алгоритмы станут гораздо проще — от обхода деревьев до динамического программирования.

Попробуй решить популярные задачи

Массивы и Хеширование