Настало время освоить рекурсию

Для программиста-самоучки задачи на рекурсию, которые нет-нет да и встречаются на собеседованиях, выглядят ужасающе. Всегда хочется найти обходной путь (например, написать цикл). Но часто, если не всегда, решение выглядит элегантнее если мы заставляем функцию вызывать саму себя, то есть делаем рекурсивное решение.

Проще говоря, рекурсия — это когда функция решает задачу, сводя ее к такой же, но чуть проще, и так до самого простого случая, решение которого заведомо известно.

Что такое рекурсия простыми словами

Рекурсия — это подход, при котором функция вызывает саму себя для решения подзадачи.

У рекурсивной функции есть две обязательные части:

1. Базовый случай (base case) — условие, когда функция перестает вызывать себя и возвращает конкретное значение
2. Рекурсивный случай (recursive case) — функция вызывает себя с другими аргументами, приближаясь к базовому случаю

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

Самый простой пример: факториал

Начнем с избитого примера, научимся искать факториал числа. Сначала напишем через цикл, а потом — рекурсивно и увидим, насколько меньше кода для этого требуется.

Итеративное решение (через цикл)

function factorial(n: number): number {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Рекурсивное решение

function factorial(n: number): number {
    // Базовый случай: если n <= 1, возвращаем 1
    if (n <= 1) {
        return 1;
    }
    // Рекурсивный случай: n умножаем на факториал (n-1)
    return n * factorialRecursive(n - 1);
}

Как это работает по шагам:

Функция множит свои вызовы в стеке, уменьшая аргумент, пока не дойдет до базового случая. Сперва каждый вызов приостанавлвиается, а потом начинается последовательный возврат значений.

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

Поиск в глубину (обход дерева)

И если с факториалом как будто есть обходные пути, то рекурсия незаменима, когда структура данных вложена неизвестно как глубоко. Например, дерево папок или комментариев.

interface Folder {
    name: string;
    children?: Folder[];
}

function printFolderTree(folder: Folder, indent: string = ''): void {
    // Выводим имя текущей папки
    console.log(indent + folder.name);
    
    // Базовый случай: если нет детей — мы закончили и выходим
    if (!folder.children || folder.children.length === 0) {
        return;
    }
    
    // Рекурсивный случай: дети есть, обходим каждого
    for (const child of folder.children) {
        printFolderTree(child, indent + '  ');
    }
}

const root: Folder = {
    name: 'Корень',
    children: [
        { name: 'Папка 1', children: [
            { name: 'Файл 1.1' },
            { name: 'Файл 1.2' }
        ]},
        { name: 'Папка 2', children: [
            { name: 'Файл 2.1' }
        ]}
    ]
};

printFolderTree(root);
// Корень
//   Папка 1
//     Файл 1.1
//     Файл 1.2
//   Папка 2
//     Файл 2.1

Хвостовая рекурсия. Небольшая оптимизация

Обычная рекурсия хранит в стеке все промежуточные вызовы. Если задача большая, стек переполняется.

Хвостовой мы называем рекурсию когда рекурсивный вызов является последней операцией в функции. Тогда компилятор может оптимизировать ее в цикл. Но, насколько мне известно, движки JS такую оптимизацию до сих пор не поддерживают. Так что эта информация скорее для общего развития.

// Обычная рекурсия
function sum(n: number): number {
    if (n <= 0) return 0;
    return n + sum(n - 1); // Последняя операция — сложение, а не вызов
}

// Хвостовая рекурсия
function sumTail(n: number, acc: number = 0): number {
    if (n <= 0) return acc;
    return sumTail(n - 1, acc + n); // Последняя операция — вызов
}

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

Предлагаю простое правило:

• Если вы работаете с сильно вложенной структурой (дерево, граф, папки) — используйте рекурсию.
• Если задача линейная (сумма чисел, факториал) — используйте цикл.

Бонусный пример: поиск файла во вложенных папках

interface FileNode {
    name: string;
    type: 'file' | 'folder';
    children?: FileNode[];
}
function findFile(node: FileNode, targetName: string): FileNode | null {
    // Базовый случай: если это файл и имя совпадает
    if (node.type === 'file' && node.name === targetName) {
        return node;
    }
    
    // Если папка — идем глубже
    if (node.type === 'folder' && node.children) {
        for (const child of node.children) {
            const result = findFile(child, targetName);
            if (result) {
                return result; // Нашли!
            }
        }
    }
    
    return null; // Не нашли
}

Итоги

• Рекурсия — это когда функция вызывает саму себя для решения подзадачи.
• Обязательны базовый случай (выход) и рекурсивный случай (приближение к выходу).
• Рекурсия идеальна для вложенных структур (деревья, папки, JSON).
• Для линейных задач (факториал, сумма) цикл работает быстрее и безопаснее.
• Хвостовая рекурсия может быть оптимизирована, но не в JS.

Рекурсия — это способ сказать: «Чтобы решить большую задачу, реши маленькую, потом добавь что-то к результату».

Желаю успехов!