Рекурсивні функції

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

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

void fn(int i)

{
     /* ... */

     fn(i);
     /* ... */
}
     Непрямою рекурсією називається рекурсія, що здійснює рекурсивний виклик функції шляхом ланцюга викликів інших функцій. При цьому всі функції ланцюга, що здійснюють рекурсію, вважаються також рекурсивними.

void fnA(int i);
void fnB(int i);
void fnC(int i);
void fnA(int i)
{
     /* ... */
     fnB(i);
     /* ... */
}
void fnB(int i)
{
     /* ... */
     fnC(i);
     /* ... */
}
void fnC(int i)
{
     /* ... */
     fnA(i);
     /* ... */
}

     Якщо функція викликає сама себе, то в стеку створюється копія значень її параметрів, як і при виклику звичайної функції, після чого управління передається першому оператору функції. При повторному виклику цей процес повторюється.
     В якості прикладу розглянемо функцію, що рекурсивно обчислює факторіал. Як відомо, значення факторіала обчислюється за формулою: n! = 1 при n=0;

n!=1x2x3x...xn

Факторіал також можна обчислити за допомогою простого рекурентного піввідношення n!=(n-1)!xn. Для ілюстрації рекурсії скористаємося саме цим співвідношенням.

Приклад 11. Обчислення факторіалу.
#include<iostream.h>
double fact(int n)
{
     if (n<=1) return 1;
     return (fact(n-1)*n);
}
void main()
{
     int n;
     double value;
     cout<<"N=";
     cin>>n;
     value=fact(n);
     cout<<"\n"<<n<<"! ="<<value;
     getch();
}

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