Рекурсія (програмування)
З Вікіпедії, безкоштовно encyclopedia
В програмуванні і інформатиці, рекурсія є методом розв'язання обчислювальної задачі[en] при якому розв'язок покладається на розв'язки менших випадків цієї ж задачі.[1][2] Рекурсія розв'язує такі рекурсивні задачі використовуючи функції чи процедури, які викликають самі себе. Цей підхід можна застосувати до багатьох задач, і рекурсія є однією з центральних ідей інформатики.[3]
Процедура рекурсивна — процедура в програмуванні, у тілі якої знаходиться явне звернення до неї самої, або через іншу процедуру.[4]
Сила рекурсії очевидно лежить в можливості визначення нескінченної множини об'єктів скінченним виразом. Таким же чином нескінченна кількість обчислень може бути описана скінченною рекурсивною програмою, навіть якщо ця програма не містить явних повторів.
Більшість мов програмування підтримують рекурсію, дозволяючи функції викликати себе з власного коду. Деякі мови функціонального програмування (наприклад, Clojure)[6] не містять ніяких конструкцій для циклів, і покладаються лише на рекурсію для багаторазового виконання коду. В теорії обчислювальності доведено що мови які містять лише рекурсію повні за Тюрінгом; це означає що вони такі ж потужні (можуть використовуватись для розв'язання таких самих задач) як і імперативні мови на основі таких структур як while
та for
.
Багаторазовий виклик функції собою може призвести до того що стек викликів матиме розмір що дорівнює сумі розмірів вхідних аргументів для всіх викликів. З цього випливає, що для задач які можна легко розв'язати ітерацією, рекурсія буде менш ефективна, і для великих задач критично використовувати методи оптимізації, такі як оптимізація хвостової рекурсії.
Застосування рекурсивних процедур, у багатьох випадках допомагає скоротити алгоритми, зробити їхню форму компактнішою.