Рекурсія

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Візуальна форма рекурсії, відома як Ефект Дроста

Рекурсія (лат. 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). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.

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

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

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

Рекурсія у фізиці[ред.ред. код]

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

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

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

Цитати[ред.ред. код]

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

Гумор[ред.ред. код]

Більшість всіх жартів про рекурсію стосується нескінченної рекурсії, у якій немає умови виходу:

  • Відоме висловлення: Щоб зрозуміти рекурсію, потрібно спочатку зрозуміти рекурсію.
  • Дуже популярний жарт про рекурсію, що нагадує словникову статтю:
    рекурсія 
    див. рекурсія
  • Кілька розповідей Станіслава Лема присвячені можливим казусам при нескінченній рекурсії:
    • Розповідь про Йона Тихого та сепульки («Зоряні щоденники Йона Тихого»), у якому герой послідовно переходить від статті про сепульки до статті про сепуляції, звідти до статті про сепулькарії, у якій знову міститься посилання до статті «сепульки».
    • Розповідь про розумну машину, що мала достатній розум і лінь, щоб для рішення поставленої задачі побудувати собі подібну, і доручити рішення їй (підсумком стала нескінченна рекурсія, коли кожна нова машина будувала собі подібну і передавала завдання їй).
  • Російська народна казка-пісня «У попа була собака…» виявляє приклад рекурсії:
    У попа була собака, він її любив
    Вона з'їла шматок м'яса, він її убив
    Убив і закопав,
    А на могилі написав:
    «У попа була собака, він її любив
    Вона з'їла шматок м'яса, він її убив
    Убив і закопав,
    А на могилі написав:
    «У попа була собака, він її любив
    Вона з'їла шматок м'яса, він її убив
    Убив і закопав,
    А на могилі написав:
    (лапки цитат ніколи не закриються)
  • Якщо в пошуковій системі Google ввести запит «рекурсія», то в пошуковій видачі побачите слова «Можливо, ви мали на увазі: рекурсія».

Див. також[ред.ред. код]