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

процесу,
при якому функція в ході виконання звертається сама до

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

рекурсивний виклик функції шляхом ланцюга викликів
інших функцій.
  Якщо

функція викликає сама себе, то в стеку
створюється копія значень її параметрів, як і при виклику
звичайної функції, після чого управління передається
першому оператору функції. При повторному виклику
цей процес повторюється.
Приклад - функція, що рекурсивно обчислює
факторіал.
n! = 1*2*3*4*…*(n-1)*n

(n

double value;       printf ("N=");      scanf ("%d", &n);      value = fact(n);      printf ("%d! = %g", n, value);      getch(); }

на
прикладі n=6 . За рекурентним співвідношенням

:
fact (n)= fact (n-1)*n .
Таким чином, щоб обчислити 6! ми спочатку повинні
обчислити 5!.   В кроках 1-5 завершення обчислення
кожний раз відкладається, а шостий крок є ключовим.
Отримане значення визначається безпосередньо, а не як
факторіал іншого числа. Відповідно, можемо
Повернутися від 6-ого кроку до 1-ого, послідовно
використовуючи значення :
6). 1!=1 5). 2!=2 4). 3!=6
3). 4!=24 2). 5!=120 1). 6!=720

серії кроків.
Перша серія - це кроки рекурсивного занурення функції

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

формула

#include
double power (double x, long

n)
{ if (n == 0) return 1;
if (n < 0) return power ( 1.0 / x, - -n);
return x * power (x, n - 1);
}
void main()
{ double x; long n;
while (scanf ("%lf %ld", &x, &n) == 2)
{ printf("%lf\n", power (x, n)); }
}

Якщо позначити стрілкою «приводимо до», тоді для першої
рекурсії отримаємо

ланцюжок довжини 12


Для другої рекурсії – послідовність з 5 кроків


Для великих значень n маємо значну перевагу. Наприклад, першою рекурсиєю обчислюється за 10000 кроків, а другою - за 19 кроків.

{
if (n == 0)

return 1;
if (n < 0) return power ( 1 / x, - -n);
if (n % 2) return x * power (x, n - 1);
return power(x * x, n / 2);
}

рекурсії
double power (double x, long n)
{

double a = 1;
while(n) {
if (n % 2)
{ a *= x;
n--; }
else
{ x *= x;
n /= 2; }
}
return a;
}