Як працює рекурсія - пояснити блок-схемами та відео

"Щоб зрозуміти рекурсію, спочатку потрібно зрозуміти рекурсію".

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

Уявіть, що ви йдете відкрити двері вашої спальні, і вони зачинені на замок. Ваш трирічний син вискакує з-за рогу і повідомляє, що він сховав єдиний ключ у коробці. («Так само, як він», - думаєш ти.) Ти спізнився на роботу, і тобі дійсно потрібно зайти в кімнату, щоб взяти сорочку.

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

Існує два основних підходи до створення алгоритму цієї проблеми: ітераційний та рекурсивний. Ось обидва підходи як блок-схеми:

Який підхід здається вам простішим?

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

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

Другий спосіб використовує рекурсію. Пам'ятайте, рекурсія - це те, коли функція викликає себе. Ось другий спосіб у псевдокоді.

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

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

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

Базовий випадок та рекурсивний випадок

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

Наприклад, ви можете написати функцію зворотного відліку. Ви можете написати це рекурсивно в JavaScript так:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

Ця функція буде продовжувати відлік назавжди. Якщо ви випадково запустили код із нескінченним циклом, ви можете натиснути “Ctrl-C”, щоб убити свій сценарій. (Або, якщо ви іноді використовуєте CodePen, як я, вам потрібно додати “? Turn_off_js = true“ в кінець URL-адреси.)

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

Ось функція зворотного відліку знову, з базовим випадком:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

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

Ми починаємо з роздрукування цифри 5 за допомогою console.log. Оскільки п'ять не менше або дорівнює нулю, ми переходимо до твердження else. Там ми знову викликаємо функцію зворотного відліку з числом чотири (5–1 = 4?).

Ми реєструємо число 4. Знову ж таки, iце не менше або дорівнює нулю, тому ми переходимо до оператора else і відлікуємо дзвінок з 3. Це триває доiдорівнює нулю. Коли це станеться, ми реєструємо число нуль , а потім iскладає менше або дорівнює нулю. Нарешті ми дістаємось до оператора return і вискакуємо з функції.

Стек дзвінків

Рекурсивні функції використовують щось, що називається "стеком викликів". Коли програма викликає функцію, ця функція надходить у стек викликів. Це схоже на стопку книг. Ви додаєте речі по черзі. Потім, коли ви готові щось зняти, ви завжди знімаєте верхній елемент.

Я покажу вам стек викликів у дії з factorialфункцією. factorial(5)записується як 5! і це визначається так: 5! = 5 * 4 * 3 * 2 * 1. Ось рекурсивна функція для обчислення факторіалу числа:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Тепер давайте подивимося, що станеться, якщо ви зателефонуєте fact(3)Ілюстрація нижче показує, як змінюється стек, рядок за рядком. Найвище вікно в стеку повідомляє вам, який дзвінок factвам наразі здійснюється.

Зверніть увагу, як кожен виклик factмає свою копію x. Це дуже важливо для того, щоб зробити роботу рекурсії. Ви не можете отримати доступ до копії іншої функції x.

Ви вже знайшли ключ?

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

Але в рекурсивному підході немає купи. Звідки ваш алгоритм знає, які ящики вам все-таки потрібно шукати? «Стопка коробок» зберігається на стосі. Це стос напівзавершених викликів функцій, кожен із яких має свій напівповний список вікон, які потрібно переглянути. Стек відстежує купу ящиків для вас!

А завдяки рекурсії ви нарешті можете знайти ключ і отримати свою сорочку!

Ви також можете переглянути це 5-хвилинне відео, яке я зробив про рекурсію. Це повинно посилити ці концепції рекурсії.

Висновок

Сподіваюся, ця стаття принесла вам більше ясності щодо рекурсії у програмуванні. Ця стаття заснована на уроці мого нового відеокурсу від Manning Publications під назвою «Алгоритми в русі». Курс (а також ця стаття) заснований на дивовижній книзі Алгоритми Грокінга Адіта Бхаргави. Саме він намалював усі цікаві ілюстрації в цій статті.

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

Знизьте 39% на мій курс, використовуючи код ' 39carnes '!

І нарешті, щоб по-справжньому зрозуміти рекурсію, ви повинні прочитати цю статтю ще раз. ?