Багатократна рекурсія

В програмуванні і інформатиці, рекурсія є методом розв'язання ^[en] при якому розв'язок покладається на розв'язки менших випадків цієї ж задачі. Рекурсія розв'язує такі рекурсивні задачі використовуючи функції чи процедури, які викликають самі себе. Цей підхід можна застосувати до багатьох задач, і рекурсія є однією з центральних ідей інформатики.

Дерево створене мовою Лого з використанням рекурсії. Кожну гілку можна розглядати як меншу версію дерева.

Процедура рекурсивна — процедура в програмуванні, у тілі якої знаходиться явне звернення до неї самої, або через іншу процедуру.

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

— Ніклаус Вірт, Algorithms + Data Structures = Programs, 1976

Більшість мов програмування підтримують рекурсію, дозволяючи функції викликати себе з власного коду. Деякі мови функціонального програмування (наприклад, Clojure) не містять ніяких конструкцій для циклів, і покладаються лише на рекурсію для багаторазового виконання коду. В теорії обчислювальності доведено що мови які містять лише рекурсію повні за Тюрінгом; це означає що вони такі ж потужні (можуть використовуватись для розв'язання таких самих задач) як і імперативні мови на основі таких структур як while та for.

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

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

Приклади

Рекурсивні процедури використовують, зокрема, для описання алгоритмів обчислення значень функцій, які задаються рекурентними співвідношеннями, наприклад:

• обчислення факторіалу n! = F(n): F(0) = 1; F(n) = n · F(n - 1)
• обчислення чисел Фібоначчі F(1) = F(2) = 1; F(n) = F(n - 1) + F(n - 2).

Види рекурсії

За рівнем рекурсії

Кількість рекурсивних входів називається рівнем рекурсії.

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

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

Множинну рекурсію іноді можна замінити одиничною (і, при потребі, ітерацією). Наприклад, наївний метод обчислення послідовності Фібоначчі використовує множинну рекурсію, так як кожне значення потребує двох попередніх, але його можна обчислити одиничною рекурсією, передаючи два послідовні значення як параметри. Більш природньо це описується корекурсією, яка накопичує результат з початкових значень, відслідковуючи два сусідні значення на кожному кроці. Див. (Корекурсія#Послідовність Фібоначчі) для прикладу. Складнішим прикладом може бути ^[en], що дозволяє здійснювати ітеративний обхід, а не тільки багатократну рекурсію.

Непряма рекурсія

Докладніше: Взаємна рекурсія

Найпростіші приклади рекурсії, і більшість прикладів тут демонструють пряму рекурсію, в якій функція викликає себе. Непряма рекурсія з'являється тоді коли функція викликається не собою, а іншою функцією, яку вона (прямо або непрямо) викликала. Наприклад, якщо f викликає f, це пряма рекурсія, але якщо в f викликає g яка викликає f, тоді це непряма рекурсія. Можливі ланцюги з більшої кількості функцій, наприклад перша функція викликає другу, друга третю і т.д, а остання - знову першу.

Непряму рекурсію також називають взаємною рекурсією. Цей термін має те ж значення, просто робить наголос на іншому аспекті. Тобто якщо f викликає g і g викликає f, з точки зору лише f, f непрямо рекурсивна. З точки зору лише g, g - непрямо рекурсивна. А з точки зору обох, чи збоку, вони взаємно рекурсивні одна для одної. Подібно множина трьох і більше функцій може називатись множиною взаємно рекурсивних функцій.

Анонімна рекурсія

Докладніше: Анонімна рекурсія

Див. також

• Рекурсія
• Хвостова рекурсія
• Рекурсивні функції (математичне визначення)
• Операція примітивної рекурсії
• Процедура (програмування)

Зноски

1. Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). 1: Recurrent Problems. Concrete Mathematics (англ.). Addison-Wesley. ISBN . Архів оригіналу за 6 листопада 2020. Процитовано 27 жовтня 2023.
2. Kuhail, M. A.; Negreiros, J.; Seffah, A. (2021). Teaching Recursive Thinking using Unplugged Activities (PDF). WTE&TE (англ.). 19: 169—175.
3. Epp, Susanna (1995). Discrete Mathematics with Applications (англ.) (вид. 2nd). PWS Publishing Company. с. 427. ISBN .
4. ЕК1973, с. 332.
5. Wirth, Niklaus (1976). Algorithms + Data Structures = Programs (англ.). Prentice-Hall. с. 126. ISBN .
6. Functional Programming | Clojure for the Brave and True. www.braveclojure.com. Процитовано 21 жовтня 2020.

Література

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973. — Т. 2.

Посилання

• IBM developerWorks: Mastering recursive programming [Архівовано 7 листопада 2006 у Wayback Machine.] — (англ.) переваги та недоліки, правила програмування рекурсивних процедур.