2. Функція факторіал n! для невід’ємних цілих чисел:

  а) 0!=1,

  б) якщо n>0, то n!=n·(n-1)!

Очевидно, що потужність рекурсії пов'язана з тим, що вона дозволяє визначити нескінченну множину об'єктів за допомогою скінченого висловлення.

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

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

Function fact (n: integer): integer;

Begin

if n>0 then

  fact:=n*fact(n-1)

else

  fact:=1

End;

Простежимо, як буде виконуватися обчислення значення 5! В операторі:

n:=fact(5);

виклик функції fact(5) буде розгорнутий у вираз 5*fact(4), тобто

n:= 5*fact(4).

Після чого знову буде викликана функція fact, але вже з аргументом 4, що приведе до подальшого розгортання виразу

n:= 5*4*fact(3);

далі  n:= 5*4*3*fact(2);

потім  n:= 5*4*3*2*fact(1);

потім  n:= 5*4*3*2*1*fact(0);

Останній виклик відповідно до алгоритму буде замінений на 1 і подальші виклики функції припиняться. Після цього вираз буде остаточно обчислений:

n:= 5*4*3*2*1*1=120

Очевидно, що даний алгоритм можна замінити звичайним ітераційним алгоритмом (ітерація  - повторення)

Function fact (k: integer): integer;

var i,n: integer;

Begin

n:=1;

for i:=2 to k  do n:=n*i;

fact:=n

End;

Випадки  застосування  рекурсії

Звичайно ітерації працюють швидше рекурсивних викликів, оскільки кожний новий виклик функції або процедури зв'язаний із запам'ятовуванням у стекові всіх регістрів стану процесора і їх відновленням при поверненні з функції або процедури. Звідси випливає висновок: варто уникати рекурсії, коли є очевидний ітеративний розв’язок поставленої задачі. Існують алгоритми, що по своїй природі скоріше рекурсивні, ніж ітераційні. Їх, природно, найкраще подавати у вигляді рекурсивних процедур. Звичайно це деякий процес, що до свого завершення вимагає повторення такого ж процесу, але з іншим параметром. З іншого боку, у деяких випадках очевидної рекурсивності алгоритму ітеративний розв’язок також буває простішим.

Приклад: Обчислення чисел Фібоначчі.

Числа Фібоначчі – це послідовність, перших два члени якої рівні 1, а решта членів визначається як  сума двох попередніх значень. Тому розрахункова формула має вигляд:

f(n) = f(n–1)+ f(n–2), n>2.

У самому визначенні чітко видно рекурсію. Однак не рекурсивний алгоритм має набагато простіший запис, і, що саме головне, працювати буде швидше. Запис такого алгоритму має вигляд:

Function fib(n:integer):integer;

Var a,b,c,i:integer;

begin

a:=1;

b:=1;

c:=1;

for i:=1 to n-2 do

begin

  c:=a+b;

  a:=b;

  b:=c;

end;

fib:=c

end;

Однак іноді рекурсивний алгоритм може виявитися простішим і більш зрозумілим. Приклад - алгоритм швидкого сортування масиву. Створення спеціальної стекової структури в ітераційному алгоритмі для заповнення частин масиву для наступної розбивки сильно ускладнює весь алгоритм.

Як і звичайний цикл з умовою, рекурсію легко зациклити, неправильно визначивши умову припинення повторних викликів. Тому за цим треба стежити особливо уважно.