Рекурсія

Матеріал з Словник з інформатики
Версія від 21:14, 26 травня 2014, створена Julia7 (обговореннявнесок)
(різн.) ← Попередня версія • Поточна версія (різн.) • Новіша версія → (різн.)
Перейти до: навігація, пошук

Рекурсія - (від латинського recursio - повернення ) - це спосіб організації обчислювального процесу , при якому метод в ході виконання обчислення звертається сам до себе. Для того, щоб таке звернення не було нескінченним , в тексті методу повинна бути умова , з досягненням якої подальшого поводження не відбувається. Рекурсії доцільно застосовувати в задачах , які можна розбити на безліч менших подібних завдань. Рекурсія в програмуванні може бути визначена як зведення задачі до такого ж завдання , але з більш простими даними.

Рекурсивний метод може викликатися як безпосередньо так і через інші методи (наприклад , метод А викликає метод B , а метод B - метод A). Кількість вкладених викликів методу називається глибиною рекурсії . Сила рекурсивного визначення об'єкта в тому , що таке кінцеве визначення здатне описувати нескінченно велика кількість об'єктів. За допомогою рекурсивної програми самостійно можливо описати нескінченне обчислення , причому без явних повторень частин програми . Рекурсія досить широко застосовується в програмуванні, що засноване на рекурсивній природі багатьох математичних алгоритмів . Також будь-який рекурсивний алгоритм можна перетворити в еквівалентний ітеративний (тобто використовує циклічні конструкції). Існує три різних форми рекурсивних програм:

1. Форма з виконанням дій до рекурсивного виклику (з виконанням дій на рекурсивному спуску).

2. Форма з виконанням дій після рекурсивного виклику (з виконанням дій на рекурсивному поверненні).

3. Форма з виконанням дій як до, так і після рекурсивного виклику (з виконанням дій, як на рекурсивному узвозі, так і на рекурсивному поверненні).


Приклад рекурсивного методу .

Для прикладу можна вирішити завдання пошуку суми цілих чисел з послідовності 1 .. n . Дана послідовність виглядає наступним чином:

1 + 2 + 3 + 4 + ... + n - 1 + n

Сума може бути представлена ​​у вигляді безлічі менших подібних завдань:

1 .. n - 1 + n ;

в цьому випадку : ( 1 + 2 + 3 + 4 + ... + n - 1 ) + n .

Дивлячись на вираз можна розділити загальну суму на дві складові частини 1 .. n - 1 - назвемо цю частину - « підсума », яка допоможе нам знайти загальну суму, все , що нам потрібно це додати до «підсуми » значення n . Нам потрібно задати базові значення, які в кінцевому рахунку, будуть досягнуті: в нашому випадку це початкові значення n -1 і n , 0 і 1 відповідно. Це дозволить нам вирішити це завдання із застосуванням рекурсії . Приклад коду описаного методу : 1. public static int sumInts(int n) {

2. // Перевірка базових значень

3. if (n == 0) { return 0; }

4. if (n == 1) { return 1; }

5. // Знаходження суми шляхом складання «підсум» и n

6. int total = sumInts(n - 1);

7. total = total + n;

8. return total;

9. }

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