16. Рекурсія. Рекурсивні алгоритми.

Рекурсивний алгоритм- це алгоритм, який при виконанні викликає самого себе. Такий алгоритм оформляється завжди як деякого допоміжного алгоритму (ВА), в С++ – це функція.

Рекурсивним може бути визначення: наприклад, натуральне число-це або 1, або ціле число, наступне за натуральним.

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

У С++ рекурсивний алгоритм оформляєтьсяу вигляді функції, назвемо їїP( ). Якщо ця функція викликає сама себеP=>P, то вона зв.прямокурсної.>Виклик може бути і опосередкованимP=>Q1=>Q2=>. =>QN=>P, у цьому випадку говорять:P–непрямо-рекурсивна.

unsigned int fact (unsigned int N)

return N* fact (N-1);

Зверніть увагу, що алгоритм містить деяку групу S пропозицій, які містять рекурсивний виклик, і групу, де є звернення до себе, тобто. P =P(S, P). При створенні рекурсивного алгоритму необхідно дбати, щоб ланцюг рекурсивних викликів не був нескінченним. Для цього рекурсивний виклик підпорядковують умові: P =P( S, if (умова) P )

Найпростіше рекурсивний виклик зв'язати з деяким параметром n, на кожному кроці цей параметр зменшуватиме:

доки стане n=0, відбувається виклик P( ).

Розглянемовиконанняалгоритмуfact(3).Це функція, у неї один формальний параметр N, інших локальних змінних немає. Виклик функції починається з того,що у певній області пам'яті- в стеку- виділяється місце під формальні параметри і локальні змінні (їх разом називають локальними змінними функції), потім виконується алгоритм функції, він знову цю функцію для параметра (N-1), тощо. для кожного дзвінка створюється своє покоління лок. даних у стеку за принципом LIFO, доступне завжди верхнє покоління.

fact(3) => fact(2) => fact(1) ) => fact(0)–рекурсивнийспуск

---