Рекурсія (лат. recursio) — метод визначення класу чи об'єкту через попереднє задання одного чи декількох (зазвичай простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.
Іншими словами, рекурсія — часткове визначення об'єкта через себе, визначення об'єкта з використанням раніше визначених. Рекурсія використовується, коли можна виділити самоподібність задачі.
Термін «рекурсія» використовується в різних спеціальних галузях знань — від лінгвістики до логіки, але найширше застосування знаходить у математиці та інформатиці. У математиці та інформатиці рекурсія пов'язана з методом визначення функцій: рекурсивно задана функція у своєму визначенні містить себе, зокрема, рекурсивною є функція, задана рекурентною формулою. Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через саму себе з використанням раніше заданих окремих визначень. З рекурсією тісно пов'язана математична індукція: вона є природним способом доведення властивостей функцій на натуральних числах, рекурсивно заданих через свої менші значення.
Визначення у логіці, що використовує рекурсію, називається індуктивним (див., наприклад, Натуральні числа).
Приклади
- Факторіал цілого невід'ємного числа n позначається n! і визначається як
- Числа Фібоначчі визначаються за допомогою рекурсії:
- Практично всі геометричні фрактали задаються у формі нескінченної рекурсії (наприклад, трикутник Серпінського).
- Задача «Ханойська вежа». Її змістовна постановка така:
Рекурсія в програмуванні
У програмуванні рекурсія — виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.
Міць рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою ж рекурсивної програми можливо описати нескінченне обчислення, причому без явних повторень частин програми.
Існує спеціальний тип рекурсії, називаний «хвостовою рекурсією». Інтерпретатори і компілятори функціональних мов програмування, що підтримують оптимізацію коду (вихідного та/або такого, що виконується), реалізують хвостову рекурсію в обмеженому обсязі пам'яті за допомогою ітерацій.
Варто уникати надлишкової глибини рекурсії, бо це може викликати переповнення стека викликів.
Рекурсія у фізиці
Класичним прикладом нескінченної рекурсії є два поставлені одне проти одного дзеркала: у них утворяться два коридори згасальних відображень дзеркал.
Іншим прикладом нескінченної рекурсії є ефект самозбудження (позитивного зворотного зв'язку) в електронних схемах посилення, коли сигнал з виходу попадає на вхід, підсилюється, знову попадає на вхід схеми і знову підсилюється. Підсилювачі, для яких такий режим роботи є штатним, називаються автогенератори.
Побутовий приклад (небажаного) самозбудження — свист у акустичних системах при завеликому підсиленні та/або невдалому розміщенні мікрофона відносно акустичних систем.
Рекурсія у природі
Яскравим прикладом явища рекурсії у природі є зовнішній вигляд капусти Романеско, яка має вигляд округлої піраміди, що формується з маленьких круглих пірамідок.
Цитати
Ітерація від людини. Рекурсія — від Бога. — Л. Пітер Дойч (Дональд Кнут. Мистецтво програмування.)
Гумор
Більшість всіх жартів про рекурсію стосується нескінченної рекурсії, у якій немає умови виходу:
- Відоме висловлення: Щоб зрозуміти рекурсію, потрібно спочатку зрозуміти рекурсію.
- Дуже популярний жарт про рекурсію, що нагадує словникову статтю:
- Кілька розповідей Станіслава Лема присвячені можливим казусам при нескінченній рекурсії:
- Оповідання про Йона Тихого та сепульки («Зоряні щоденники Йона Тихого»), у якій герой послідовно переходить від статті про сепульки до статті про сепуляції, звідти до статті про сепулькарії, у якій знову міститься посилання на статтю «сепульки».
- Оповідання про розумну машину, що мала достатній розум і лінь, щоб для розв'язання поставленої задачі побудувати собі подібну, і доручити розв'язування їй (підсумком стала нескінченна рекурсія, коли кожна нова машина будувала собі подібну і передавала задачу їй).
- Російська народна казка-пісня «У попа була собака…» є прикладом рекурсії:
- (лапки цитат ніколи не закриються)
- Якщо в пошуковій системі Google ввести запит «рекурсія», то в пошуковій видачі побачите слова «Можливо, ви мали на увазі: рекурсія».
Література
- Елементи математичної логіки та теорії рекурсії : навч. посіб. / М. Комарницький, В.Андрійчук , І.Мельник. – Львів : ЛНУ імені Івана Франка, 2013. – 282 с.
Примітки
- Hunter, David (2011). . Jones and Bartlett. с. 494. Архів оригіналу за 1 квітня 2017. Процитовано 16 лютого 2016.
Див. також
- Корекурсія
- Міз-ан-абім
- Фрактал
- Автореференція
- Непредикативність (математика)
- Рекурсивна процедура
- Рекурсивні функції — використовуються в математиці, зокрема, в теорії алгоритмів, для визначення класу обчислюваних функцій.
- Універсальні рекурсивні функції
- Ітерація
- Теорія обчислюваності
Ця стаття не містить посилань на джерела. (лютий 2013) |
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |