Глава 3

Факториал целого числа, number, большего или равного 0, может быть вычислен итеративно (нерекурсивно) с помощью оператора for следующим образом:

factorial = 1;

for (int counter = number; counter >=1; counter--) factorial *= counter;

Рекурсивное определение функции факториал дается следующим соот­ношением:

n\=nx(n-l)l

Например, факториал 5! очевидно равен 5x4!. В самом деле:

5!=5x4x3x2xl

5!=5x(4x3x2xl)

5!=5x4!

Вычисление 5! должно происходить в соответствии с рис. 3.13. Рис. 3.13a показывает, как протекает последовательность рекурсивных вызовов до тех пор, пока не будет вычислен 1! = 1, что приведет к завершению рекурсии. Рис. 3.136 показывает значения, возвращаемые из каждого рекурсивного вызова оператору вызова до тех пор, пока не будет вычислено и возвращено окончательное значение.

2! = 2 * 1 = 2 возвращается

возвращено

а) Процесс рекурсивных вызовов