12 лист. 2025 р.

Дейкстра мав рацію — рекурсія не повинна бути складною

Майже кожна мова програмування має різні керуючі структури, такі як блоки if…else/switch…case, і ітераційні структури, такі як цикли for і while. Більшість нових програмістів спочатку вивчають ітераційні керуючі структури.

Але є ще одна дуже потужна структура контролю: recursion. Рекурсія є однією з найважливіших ідей в інформатиці, але зазвичай її вважають однією з складних для розуміння частин програмування. Книги часто вводять його набагато пізніше, ніж ітераційні керуючі структури.

Кількість запитань в Інтернеті, які запитують, чому рекурсія або рекурсивні програми такі важкі для розуміння, можуть створити у вас враження, що рекурсія справді є передовою технікою. Але це не повинно бути важко.

Хоча для того, щоб розпізнати рекурсивну природу проблеми та знайти рішення, потрібен інстинкт, цьому можна навчитися на практиці. Ця стаття представить і пояснить низку тем та ідей, які допоможуть вам під час практики рекурсивних задач.

Навіщо використовувати рекурсію?

Можливо, ви чули цей жарт — щоб зрозуміти рекурсію, ви повинні спочатку зрозуміти рекурсію. Це відповідає загальноприйнятому визначенню рекурсії як функції, яка викликає саму себе.

Таке визначення може створити у вас враження, що такі виклики призводять до нескінченного регресу, але правильно визначене рекурсивне рішення ніколи не буває нескінченним. Це пояснюється тим, що рекурсивна підфункція ніколи не вирішує ту саму проблему, що й оригінальна функція, а завжди є простішою версією вихідної проблеми. У якийсь момент ця версія стає настільки простою, що її можна легко вирішити, і саме тоді рекурсія закінчується.

Це веде нас до найважливішого випадку використання рекурсії: використовуйте рекурсію, щоб зменшити складність поточної проблеми.

Давайте розглянемо приклад. Припустімо, ви хочете обчислити суму всіх елементів у масиві, який має вкладені підмасиви. Таким чином, якщо функція отримує такі вкладені масиви:

[1,[11,42,[8, 1], 4, [22,21]]]

він повертає суму всіх елементів:

1+11+42+8+1+4+22+21 = 110.

Хитрість полягає в тому, щоб ідентифікувати та розв’язати простішу задачу, а потім виразити проблему в термінах цього простішого випадку. Потім ви застосовуєте рекурсію, доки цей випадок не буде досягнуто та розв’язано. І разом з цим усі інші рекурсивні кроки до вашої вихідної проблеми також вирішуються.

Найпростішим випадком розглянутої проблеми є масив без вкладених підмасивів. Для такого масиву обчислювальна функція може виглядати так:

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        result += a[i];
    }
    return result;
}

assert.equal(sum([1, -5, 100]), 96);

Тепер у нас є функція sum, яка приймає масив і повертає суму всіх його елементів. Давайте розв’яжемо оригінальну складнішу задачу. У ньому зазначено, що деякі елементи можуть бути масивами, тоді як поточна реалізація передбачає, що всі елементи в масиві є числами. Тому нам просто потрібно перевірити, чи є елемент масивом чи ні, і якщо це масив, у нас уже є функція sum для обчислення суми всіх елементів у цьому масиві. Давайте трохи налаштуємо нашу функцію sum:

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        if (Array.isArray(a[i])) {
            result += sum(a[i])
        } else {
            result += a[i];
        }
    }
    return result;
}

assert.equal(sum([1,[11,42,[8, 1], 4, [22,21]]]), 110);

Це все. Ми розв’язали простішу задачу й використали її для складнішої. Також можливе ітераційне рішення: явний стек може містити масиви, які ще потрібно відвідати. Рекурсія обробляє цю бухгалтерію через стек викликів, що робить цю версію особливо прямою.

Крім того, що допомагає зменшити складність проблеми, рекурсія має ще одну важливу можливість, а саме здатність зворотного шляху. Проблеми, які вимагають зворотного відстеження, зазвичай стосуються крокуючих дерев/графів, наприклад, різних видів лабіринтів. Такі проблеми вирішуються крок за кроком. Ось загальний алгоритм:

Якщо поточний крок алгоритму є рішенням задачі, повернути результат.
Якщо поточний крок не є рішенням, подивіться, чи є інші місця, куди можна піти звідси.
Якщо ще є місця, куди можна піти, виберіть одне й перейдіть туди, щоб перевірити, чи це рішення.
Якщо куди їхати немає — повертайтеся назад.

Давайте розглянемо приклад. Нам дано таке дерево:

Він представлений у вигляді вузлів із дочірніми елементами:

let tree = {
    name: 'A',
    value: 4,
    children: [
        {
            name: 'B', value: 7,
            children: [{name: 'C', value: 9, children: []}]
        },
        {
            name: 'D', value: 11,
            children: [{name: 'E', value: 9, children: []}]
        },
        {name: 'F', value: 55, children: []},
        {
            name: 'G', value: 65,
            children: [
                {name: 'H', value: 21, children: []},
                {name: 'I', value: 33, children: []}
            ]
        }
    ]
};

І завдання знайти вузол зі значенням 21.

Отже, ось як ми збираємося це зробити:

Спочатку перевірте вузол A.
Якщо це не те, що ми шукаємо, ми можемо перейти до B, потім до C.
Жоден вузол на нашому шляху не задовольняє рівності, і звідси нікуди подітися, тому ми повертаємося назад до A.
Потім ми перевіряємо D і E. Не пощастило.
Відкат. F.
Поверніться знову. Перевірте G. Все одно не пощастило.

Але нам ще є куди піти. Нарешті H. Це вузол, який ми шукаємо.

А ось проста реалізація:

function find(node, value) {
    if (node.value === value) {
        return node;
    } else {
        for (let i = 0; i < node.children.length; i++) {
            let found = find(node.children[i], value);
            if (found !== null) {
                return found;
            }
        }

        return null;
    }
}

assert.equal(find(tree, 21).name, 'H');

Розробка рішення

Поширена помилка новачків, розробляючи рішення рекурсивної проблеми, полягає в тому, що вони намагаються уявити, що відбувається всередині рекурсивного виклику, замість того, щоб просто вірити, що він поверне правильний результат. В задачі з вкладеними масивами для розв

if (Array.isArray(a[i])) {
    result += sum(a[i]);
}

не думайте, що станеться після виконання функції sum. Це не корисний спосіб думати про рекурсію. Натомість вірте, що він повертає правильну суму для всіх елементів масиву a[i]. Крім того, не думайте про рекурсивну програму як про серію кроків виконання і спробуйте реконструювати дерево виконання у своїй голові. Для деяких складних проблем це буде дуже важко і не допоможе вам знайти рішення.

Коли ви починаєте працювати над рішенням, подумайте про те, як вихідну задачу можна представити у вигляді простішої задачі з деякими додатковими операціями. Ідентифікація цієї простішої проблеми є, мабуть, найскладнішою частиною розв’язання рекурсивної задачі. Це може бути тривіально для деяких легких задач, подібних до тих, які ми використовували в прикладах вище, але для багатьох складніших задач розпізнавання шаблону потребує навичок. Чим більше ви практикуєтеся, тим краще у вас це виходить.

Після того, як ви визначили простішу проблему, перейдіть до пошуку найпростішої проблеми, яку ваша функція повинна буде вирішити. Ця найпростіша задача називається базовим випадком. Зазвичай це представляється як форма умови, яка завершує рекурсію. У наших попередніх прикладах він постає у вигляді циклу for, який перевіряє, чи є елементи в масиві (сума) або дочірні елементи у вузлі (знайти). Іноді в легких задачах простішою проблемою, яка допомагає розв’язати початкову задачу, є також базовий випадок. Але це не так із складнішими проблемами, такими як ця знаменита проблема «Ханойської вежі»:

У вас є три стрижня і кілька дисків різного розміру, які можна перемістити на будь-який стрижень. Ви починаєте з дисків у акуратному стосі в порядку зростання розміру на одному стрижні. Мета гри полягає в тому, щоб перемістити всі диски до вежі 3. Але ви можете переміщати лише один диск за раз і не можете помістити більший диск на менший.

Ця простіша проблема, яку ви повинні побачити тут:

Перемістіть диски n-1 на допоміжний стрижень.

Перемістіть останній диск від джерела до цільового стрижня.

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

Тут важливо не продумувати кроки, як диски переміщуються до допоміжного стрижня, а припустити, що якщо вони вже переміщені туди, ми можемо перемістити останній диск, а потім перемістити решту дисків. Отже, давайте напишемо код для цього випадку:

function move(n, src, aux, dest) {

    // move all disks but the last from source to auxiliary rod,
    // that's why aux and dest rods are swapped in a function call
    // so that aux rod becomes the destination
    move(n - 1, src, dest, aux);

    // move the last disk from source to destination rod
    dest.push(src.pop());

    // move the remaining disks from auxiliary to target rod,
    // that's why aux and src rods are swapped in a function call
    // so that auxiliary rod becomes the source
    move(n - 1, aux, src, dest);
}

Тепер, коли у нас є простіша задача, нам потрібно знайти найпростіший базовий випадок. І це, напевно, легко помітити:

Якщо у нас залишився один диск, просто перемістіть його на цільовий стержень:

function move(n, src, aux, dest) {
    if (n === 1) {
        dest.push(src.pop());
    } else {
        move(n - 1, src, dest, aux);
        dest.push(src.pop());
        move(n - 1, aux, src, dest);
    }
}

І це базовий випадок, який завершує рекурсію. І це не та сама простіша задача, яка допомагає розв’язати початкову проблему.

Тепер спробуйте застосувати те, що ви дізналися вище, до таких проблем:

Знаходження суми вкладених масивів

Напишіть функцію, яка підсумовує всі числа в масиві, який може мати вкладені підмасиви. Не використовуйте петлі.

Генерація двійкових рядків

Напишіть функцію, яка генерує всі можливі комбінації 1 і 0 для n бітів. Наприклад, якщо функція отримує 2 як кількість бітів, вона має створити такі 4 комбінації: 00,01,10,11. Генеруйте рядки рекурсивно, а не шляхом перетворення цілочисельних лічильників у двійкові.

Намагаючись придумати рішення, спробуйте думати про рішення, визначаючи простішу проблему та базовий варіант, а не будуючи крок за кроком потік виконання. Крім того, спробуйте подумати, що зараз ви дивитеся на проміжний крок, яку наступну операцію вам слід виконати, щоб просунутися до рішення.

Перевірте рішення та пояснення в кінці статті.

Оптимізація хвостового виклику

Можливо, ви чули термін call stack. Здебільшого він використовується під час налагодження, щоб зрозуміти, як була викликана функція, яка породила помилку. Отже, якщо у вас є такий код у файлі index.js:

function a(n) {
    let a = 1;
    return a + n;
}

function b(n) {
    let b = 5;
    let value = a(n);  // line B
    return b + value;
}

function c() {
    let c = 3;
    let v = b(c);  // line C
    console.log(v);
}

c();  // line A

і помістіть точку зупину всередині a, ви матимете стек викликів, який виглядає приблизно так:

a() (return to: {b(): B}, locals: {a=1, n=3})
b() (return to: {c(): C}, locals: {b=5, n=3})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

У якому зазначено, що функція a була викликана з b, а b з c. Ось звідки походить стек викликів імен — стек викликів функцій. Кожен запис у стеку називається стековим кадром і містить, серед іншого, таку інформацію: локальні змінні та адресу повернення (до якої повертаються, коли поточна функція завершує роботу). Важливо те, що кількість і розмір кадрів у стеку обмежено. Це означає, що якщо ви продовжуєте викликати функції достатньо разів, ви отримаєте помилку переповнення стека. Це обмеження не є фіксованим і залежить від середовища до середовища та залежить від розміру кадру кожної окремої функції.

Рекурсивна функція постійно викликає сама себе багато разів, тому існує потенційний ризик помилки переповнення стека. Наприклад, ця проста рекурсивна функція обчислює факториал числа:

function fact(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return n * fact(n - 1);
}

Якщо ми передаємо досить велике число, наприклад, 100 000, ми отримаємо помилку в більшості середовищ. Цю рекурсивну реалізацію факторіала зазвичай не рекомендують як приклад рекурсії, оскільки того самого результату можна легко досягти за допомогою ітераційних рішень. Окрім потенційної помилки переповнення стеку, це рекурсивне рішення збільшує продуктивність, використовуючи додаткові кадри стека та, як наслідок, займаючи більше пам’яті.

Рекурсія є ідіоматичною в багатьох функціональних мовах, а такі мови, як Scheme, гарантують правильні хвостові виклики. Це допомагає лише тоді, коли рекурсивний виклик знаходиться в кінцевій позиції; факторіал вище не є, тому що він все ще множиться після повернення виклику. Давайте спочатку відрефакторимо попередній приклад стеку викликів:

function a(n, p) {
    let a = 1;
    return a + n + p;
}

function b(n) {
    let b = 5;
    return a(n, b);
}

function c() {
    let c = 3;
    let v = b(c);  // line C
    console.log(v);
}

c();  // line A

Коли b викликає тут a, у нього більше немає роботи. Реалізація з відповідними кінцевими викликами може замінити стековий фрейм b на a, зберігаючи вихідну адресу повернення. Тоді стек виглядатиме так:

a() (return to: {c(): C}, locals: {a=1, n=3, p=5})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

Подивіться на відмінності у функції b до та після рефакторингу:

// without tail-call optimization
let value = a(n);
return b + value;

// with tail-call optimization
return a(n, b);

Отже, основна відмінність полягає в тому, що після повернення функції a немає інших дій. Давайте перепишемо нашу факторіальну функцію, щоб мати право на оптимізацію хвостового виклику:

function fact(acc, n) {
    if (n === 0 || n === 1) {
        return acc;
    } else {
        return fact(acc * n, n - 1);
    }
}

Як бачите, замість того, щоб брати значення, що повертається, і обчислювати результат після повернення рекурсивного виклику, ми спочатку обчислюємо його та переходимо до наступного рекурсивного виклику. Отже, у першій реалізації без оптимізації хвоста ви спочатку виконуєте рекурсивні виклики, а потім берете значення, що повертається рекурсивним викликом, і обчислюєте результат. Таким чином, ви не отримаєте результат свого обчислення, доки не повернетеся з кожного рекурсивного виклику.

Щоб перетворити реалізацію на хвостову рекурсію, ви спочатку виконуєте обчислення, а потім виконуєте рекурсивний виклик, передаючи результати вашого поточного кроку до наступного рекурсивного кроку. Це призводить до того, що останній рекурсивний виклик просто повертає накопичене значення, коли умова виконується. Загалом, значення, що повертається будь-яким заданим рекурсивним кроком, таке ж, як значення, що повертається наступним рекурсивним викликом. Наслідком цього є те, що як тільки ви будете готові виконати свій наступний рекурсивний крок, вам більше не потрібен поточний кадр стека.

Стиль передачі продовження (CPS) виражає роботу, що залишилася, як функцію, передану до наступного виклику. Він може виявляти кінцеві виклики, але самі по собі зворотні виклики не гарантують постійного використання стека. JavaScript визначає відповідні хвостові виклики для придатних викликів строгого режиму; WebKit реалізує їх, але підтримку не можна переносити на інші механізми. Використовуйте ітераційну версію, коли використання обмеженого стеку має працювати всюди.

Рішення

Отже, ось перша проблема:

Напишіть функцію, яка підсумовує всі числа в масиві, який може мати вкладені підмасиви. Не використовуйте петлі.

Ми можемо почати з визначення простішої проблеми — це масив без вкладених підмасивів. Давайте поставимо ті самі питання, щоб вирішити цю простішу задачу:

Яка проблема простіша? Простіша проблема полягає в тому, що у мене є сума елементів n-1 і потрібно лише додати поточний елемент до цієї суми.
Який найпростіший випадок? Найпростіший випадок, коли не залишилося елементів для додавання — поверніть 0.

Отже, ось реалізація:

function sum(a, i) {
    if (i < 0) {
        return 0;
    } else {
        return a[i] + sum(a, i - 1);
    }
}

let input = [1, 2, 0, 3];
assert.equal(sum(input, input.length - 1), 6);

Тепер ми розв’язали простішу проблему без вкладених масивів. Нам потрібно враховувати вкладені масиви. Нам потрібно перевірити, чи є елемент масивом, і якщо так, просто запустіть для нього функцію sum. Тут важливо не забути отримати суму елементів у вкладеному підмасиві та додати її до результуючого значення. Отже, ось остаточна реалізація:

function sum(a, i) {
    if (i < 0) {
        return 0;
    }

    let current = a[i];

    if (Array.isArray(a[i])) {
        current = sum(a[i], a[i].length - 1);
    }

    return current + sum(a, i - 1);
}

let input = [1, 2, [1, 2], 3, [5]];
assert.equal(sum(input, input.length - 1), 14);

Тепер розглянемо другу проблему:

Напишіть функцію, яка генерує всі можливі комбінації 1 і 0 для n бітів. Наприклад, якщо функція отримує 2 як кількість бітів, вона має створити такі 4 комбінації: 00,01,10,11. Генеруйте рядки рекурсивно, а не шляхом перетворення цілочисельних лічильників у двійкові.

Який тут найпростіший випадок? Нам потрібно створювати рядки лише для одного біта. Для цього у нас буде два рядки 1 і 0. Отже, у нас є функція, яка виводить 1 і 0, якщо кількість бітів 1. Давайте запишемо це, припускаючи, що існує глобальна змінна a, яка містить масив:

function binary(n) {
    if (n === 1) {

        a[n - 1] = 0;
        console.log(a.join(''));

        a[n - 1] = 1;
        console.log(a.join(''));
    }
}

Ця поточна реалізація містить повторюваний оператор console.log, тож ми можемо вдосконалити код, виконавши реєстрацію як останню операцію, коли більше немає бітів для встановлення. Давайте перепишемо реалізацію:

function binary(i) {
    if (i === 0) {
        console.log(a.join(''));
    } else {
        a[i - 1] = 0;
        binary(i - 1);
        a[i - 1] = 1;
        binary(i - 1);
    }
}

Тепер давайте подивимося, які комбінації будуть там для 2 бітів.

Отже, ми починаємо без встановлення бітів. Потім ми встановлюємо біт 0 для біта n. Потім ми робимо те саме для біта n-1. Ми дотримуємося цього шаблону, доки більше не залишиться бітів для встановлення. Ми друкуємо комбінацію і повертаємося на рівень вище. Потім ми встановлюємо біт n на 1. Зрозуміло, що на кожному кроці функція займається лише встановленням поточного біта та викликом функції для обробки решти бітів.

І це те, що ми вже маємо в нашій реалізації для обробки одного біта. Як виявилося, шляхом простого рефакторингу базового випадку ми дійшли до рішення, яке працюватиме для будь-якої кількості бітів.

Дейкстра мав рацію — рекурсія не повинна бути складною

Навіщо використовувати рекурсію?

Розробка рішення

Оптимізація хвостового виклику

Рішення

Підпишіться на нові статті:

Будьте в курсі подій