Рекурсія

Візуальна форма рекурсії, відома як Ефект Дроста

Рекурсія (лат. Recursion)— метод визначення класу чи об'єктів методів попереднім заданням одного чи декількох (звичайно простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.

Іншими словами, рекурсія — часткове визначення об'єкта через себе, визначення об'єкта з використанням раніше визначених. Рекурсія використовується, коли можна виділити самоподібність задачі.

Визначення у логіці, що використовує рекурсію, називається індуктивним (див., наприклад, Натуральне число).

Приклади

• Факторіал цілого невід'ємного числа n позначається n! і визначається як

  n!=n×(n-1)! при n>0 і n!=1 при n=0

• Числа Фібоначчі визначаються за допомогою рекурсії:

  перше і друге числа Фібоначчі рівні 1;

  для n>2, n-і число Фібоначчі дорівнює сумі (n-1)-го і (n-2)-го чисел Фібоначчі.

Трикутник Серпінського

• Практично всі геометричні фрактали задаються у формі нескінченної рекурсії (наприклад, трикутник Серпінського).
• Задача «Ханойська вежа». Її змістовна постановка така:

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

  Рекурсивний варіант розв'язку задачі:

  Потрібно застосувати рекурсивно алгоритм, переклавши n-1 кільце з першої піраміди на третю піраміду. Потім зробити очевидний хід, переклавши останнє найбільше кільце з першої піраміди на другу. Потім знову застосувати рекурсію, переклавши n-1 кільце з третьої піраміди на другу піраміду.

Рекурсія в програмуванні

У програмуванні рекурсія — виклик функції чи процедури з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.

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

Існує спеціальний тип рекурсії, називаний «хвостовою рекурсією». Інтерпретатори і компілятори функціональных мов програмування, що підтримують оптимізацію коду (вихідного і/чи що виконується), виконують хвостову рекурсію в обмеженому обсязі пам'яті за допомогою ітерацій.

Варто уникати надлишкової глибини рекурсії, тому що це може викликати переповнення стека викликів.

Рекурсія у фізиці

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

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

Побутовий приклад (небажаного) самозбудження — свист у акустичних системах при занадто великому підсиленні та/або невдалому розміщенні мікрофона відносно акустичних систем.

Цитати

Ітерація від людини. Рекурсія — від Бога. — Л. Пітер Дойч (Д. Кнут. Мистецтво програмування.)

Гумор

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

рекурсія

див. рекурсія

Кілька розповідей Станіслава Лема присвячені можливим казусам при нескінченній рекурсії:

• Розповідь про Йона Тихого та сепульки («Зоряні щоденники Йона Тихого»), у якому герой послідовно переходить від статті про сепульки до статті про сепуляції, звідти до статті про сепулькарії, у якій знову міститься посилання до статті «сепульки».
• Розповідь про розумну машину, що мала достатній розум і лінь, щоб для рішення поставленої задачі побудувати собі подібну, і доручити рішення їй (підсумком стала нескінченна рекурсія, коли кожна нова машина будувала собі подібну і передавала завдання їй).

Російська народна казка-пісня «У попа була собака…» виявляє приклад рекурсії:

У попа була собака, він її любив
Вона з'їла шматок м'яса, він її убив
Убив і закопав,
А на могилі написав:

"У попа була собака, він її любив

Вона з'їла шматок м'яса, він її убив

Убив і закопав,

А на могилі написав:

"У попа була собака, він її любив

Вона з'їла шматок м'яса, він її убив

Убив і закопав,

А на могилі написав:

…

(лапки цитат ніколи не закриються)

Див. також

• Корекурсія
• Міз-ан-абім
• Автореференція
• Рекурсивна процедура
• Рекурсивні функції — використовуються в математиці, зокрема, в теорії алгоритмів, для визначення класу обчислюваних функцій.
• Ітерація
• Теорія обчислюваності