Рекурсивна функція

Рекурсивна функція (від recursio - Повернення) - це числова функція f (n) числового аргументу, яка в своєму записі містить себе ж. Такий запис дозволяє обчислювати значення f ( n ) на основі значень f ( n − 1 ) , f ( n − 2 ) , … , подібно до міркування щодо індукції. (наприклад, для n = 0, 1). Ось приклад рекурсивної функції, що дає n-е число Фібоначчі:

Керуючись цим записом, ми можемо обчислити F (n) для будь-якого натурального n за кінцеве число кроків. Правда, по дорозі доведеться додатково обчислити значення F (n - 1), F (n - 2), ..., F (2), У зв'язку з цими накладними витратами корисно знати, чи є у рекурсивної функції нерекурсивна (замкнута) форма.

Наприклад, рекурсивна функція:

може бути переведена в замкнуту форму: f = n (n + 1) 2>. Замкнену форму можна знайти не для всіх рекурсивних функцій (співвідношень). Для деяких із них знайдено лише наближені замкнуті форми. Деякі рекурсивні співвідношення, такі як факторіал, є елементарними математичними операціями.

Рекурсивні функції відіграють у теорії алгоритмів, оскільки багато алгоритмів мають рекурсивну структуру.

is:Endurkvæmt fall pl:Funkcja rekurencyjna

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

До вашої уваги переклад статті Beau Carnes How Recursion Works — explained with flowcharts and a video.

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

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

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

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

Який підхід для Вас найпростіший?

У першому підході використовується цикл, коли. Тобто. поки стопка коробок повна, хапай наступну коробку і дивися всередину неї. Нижче трохи псевдокода на 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: Ця функція contains an infinite loop! function countdown(i) < console.log(i) countdown(i - 1) >countdown(5); // Це є початковий телефон до функції.

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

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

І знову функція підрахунку, тільки з граничним випадком:

function countdown(i) < console.log(i) if (i else < // recursive case countdown(i - 1) >> countdown(5);

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

Спочатку ми виведемо цифру 5, використовуючи команду Console.Log. Т.к. 5 не менше або одно 1, то ми перейдемо в блок else. Тут ми знову викличемо функцію і передамо до неї цифру 4 (бо 5 – 1 = 4).

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

Стек викликів

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

Я продемонструю вам стек викликів у дії, використовуючи функцію підрахунку факторіалу. 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.

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

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

Але в рекурсивному підході немає чарки.То як тоді алгоритм розуміє у якій коробці слід шукати? Відповідь: «Стопка коробок» зберігається в стеку. Формується стек із наполовину виконаних звернень до функції, кожне з яких містить свій наполовину виконаний список із коробок для перегляду. Стек стежить за чаркою для Вас!

І так, завдяки рекурсії, Ви нарешті змогли знайти свій ключ і взяти сорочку!

Ви також можете переглянути моє п'ятихвилинне відео про рекурсію. Воно має посилити розуміння наведених тут концепцій.

Висновок від автора

Сподіваюся, що стаття внесла трохи більше ясності у Ваше розуміння рекурсії у програмуванні. Основою статті послужив урок у моєму новому відео курсі від Manning Publications під назвою «Algorithms in Motion». І курс та стати написані за чудовою книгою «Grokking Algorithms», автором якої є Adit Bhargava, ким і були намальовані всі ці чудові ілюстрації.

І нарешті, щоб справді закріпити свої знання про рекурсію, Ви повинні прочитати цю статтю як мінімум ще раз.

Від себе хочу додати, що з цікавістю спостерігаю за статтями та відеоуроками Beau Carnes, і сподіваюся, що Вам теж сподобалася стаття і особливо ці справді чудові ілюстрації з книги A. Bhargav «Grokking Algorithms».