Рекурсія

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

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

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

 

• Факторіал цілого невід'ємного числа 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 ввести запит «рекурсія», то в пошуковій видачі побачите слова «Можливо, ви мали на увазі: рекурсія».

• Елементи математичної логіки та теорії рекурсії : навч. посіб. / М. Комарницький, В.Андрійчук , І.Мельник. – Львів : ЛНУ імені Івана Франка, 2013. – 282 с.

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

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.