Одним із найпростіших прикладів рекурсії може стати функція обчислення факторіала. Нагадаємо, що факторіалом пі натурального числа п! називається добуток усіх цілих чисел від одиниці до n. Вважають також, що 0!=1. Існує нерекурсивний спосіб обчислення факторіала за допомогою циклу:
Factorial :=1;
for і :=2 to n do
factorial := factorial*1;
Наведений код реалізує такий принцип обчислень. Покладемо спочатку 1!=1, потім 1! помножимо на 2 і отримаємо 2!, потім 2! помножимо на З і отримаємо З! тощо. Отже, обчислення факторіала зводиться до багаторазового застосування рекурентної формули n! = (n - 1)!*n. Ця формула є рекурсивною, оскільки означує «факторіал через факторіал».
Реалізуємо щойно наведене означення рекурсивною процедурою у програмі
Var
n:integer; {число, факторіал якого необхідно обчислити}
function F(n:integer):integer; {оголошення функції}
begin
if n = 0 then F:=1
else F:=F(n-l)*n; {рекурсивний виклик функції}
end:
begin {основна програма}
writeln (‘Enter n ‘);
readln (n);
writeln (‘n! = ‘, F(n)) ;
end.