Loading AI tools
процес повторення предметів самоподібним чином/способом З Вікіпедії, вільної енциклопедії
Рекурсія (лат. recursio) — метод визначення класу чи об'єкту через попереднє задання одного чи декількох (зазвичай простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.
Іншими словами, рекурсія — часткове визначення об'єкта через себе, визначення об'єкта з використанням раніше визначених. Рекурсія використовується, коли можна виділити самоподібність задачі.
Термін «рекурсія» використовується в різних спеціальних галузях знань — від лінгвістики до логіки, але найширше застосування знаходить у математиці та інформатиці. У математиці та інформатиці рекурсія пов'язана з методом визначення функцій: рекурсивно задана функція у своєму визначенні містить себе, зокрема, рекурсивною є функція, задана рекурентною формулою. Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через саму себе з використанням раніше заданих окремих визначень. З рекурсією тісно пов'язана математична індукція: вона є природним способом доведення властивостей функцій на натуральних числах, рекурсивно заданих через свої менші значення.
Визначення у логіці, що використовує рекурсію, називається індуктивним (див., наприклад, Натуральні числа).
У програмуванні рекурсія — виклик підпрограми (функції чи процедури) з неї самої (звичайно з іншими значеннями вхідних параметрів) безпосередньо чи через інші функції (наприклад, функція А викликає функцію B, а функція B — функцію A). Кількість вкладених викликів функції чи процедури називається глибиною рекурсії.
Міць рекурсивного визначення об'єкта в тім, що таке кінцеве визначення здатне описувати нескінченно велике число об'єктів. За допомогою ж рекурсивної програми можливо описати нескінченне обчислення, причому без явних повторень частин програми.
Існує спеціальний тип рекурсії, називаний «хвостовою рекурсією». Інтерпретатори і компілятори функціональних мов програмування, що підтримують оптимізацію коду (вихідного та/або такого, що виконується), реалізують хвостову рекурсію в обмеженому обсязі пам'яті за допомогою ітерацій.
Варто уникати надлишкової глибини рекурсії, бо це може викликати переповнення стека викликів.
Класичним прикладом нескінченної рекурсії є два поставлені одне проти одного дзеркала: у них утворяться два коридори згасальних відображень дзеркал.
Іншим прикладом нескінченної рекурсії є ефект самозбудження (позитивного зворотного зв'язку) в електронних схемах посилення, коли сигнал з виходу попадає на вхід, підсилюється, знову попадає на вхід схеми і знову підсилюється. Підсилювачі, для яких такий режим роботи є штатним, називаються автогенератори.
Побутовий приклад (небажаного) самозбудження — свист у акустичних системах при завеликому підсиленні та/або невдалому розміщенні мікрофона відносно акустичних систем.
Яскравим прикладом явища рекурсії у природі є зовнішній вигляд капусти Романеско, яка має вигляд округлої піраміди, що формується з маленьких круглих пірамідок.
Ітерація від людини. Рекурсія — від Бога. — Л. Пітер Дойч (Дональд Кнут. Мистецтво програмування.)
Більшість всіх жартів про рекурсію стосується нескінченної рекурсії, у якій немає умови виходу:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.