13.2. Обчислення факторіала

Задача

Надано число n. Обчислити n!.

Алгоритм

Факторіал n! визначається як добуток такого виду:

n! = 123 ... n .

При цьому вважається, що 0! = 1. Із наведеного визначення виходить, що для обчислення факторіалу можна застосувати таке правило:

Як ми бачимо, наведене правило є рекурсивним. Звідси для обчислення факторіалу одразу маємо рекурсивний алгоритм. Реалізація його у вигляді функції r_factorial виглядає так:

long r_factorial(long n)

{ if ( n==0 || n==1 ) return 1;

else return (n*r_factorial(n-1));

}

Очевидно, що при обчисленні n! глибина рекурсії буде дорівнювати n. Циклічний варіант функції обчислення факторіалу буде виглядати так:

long с_factorial(long n)

{ long fact = 1;

for (long i=2; i<=n; i++) fact *= i;

return fact;

}