Рассмотрим функцию вычисления факториала:
int fact(int x)
{
if(x==0) return 1;
if(x==1) return 1;
int y=fact(x-1);
printf("x=%i, y=%i\n", x, y);
return x*y;
}
void main()
{
fact(5);
}
Эта функция рекурсивная, т. е. вызывает сама себя, она реализует факториал по его определению, т. е. факториал от 0 или 1 равен 1, а факториал от другого целого числа равен произведению этого числа на факториал от числа на единицу меньше. В рассматриваемой функции есть дополнительные строчки, которые печатают на каждом шаге само число, и факториал от числа на единицу меньше.
Большинство циклов можно записать в рекуррентной или итеративной формах. Рекуррентная форма использует рекурсивные функции, а итеративная находит нужное значение пошагово.
В рекуррентной форме удобно записывать большинство алгоритмов. Эта форма более соответствует человеческому мышлению, чем запись алгоритма в виде цикла. В результате возникает задача преобразования рекуррентной формы в итеративный цикл.
Рассмотрим работу этой функции для случая вычисления факториала 5:
|
|
x=2, y=1
x=3, y=2
x=4, y=6
x=5, y=24
Заметим, что на каждом шаге цикла выполняются определенные условия, их можно записать следующим образом: y = (x – 1)!. Условие, которое выполняется на каждом шаге цикла, называется инвариантом. Данное условие выполняется в самом начале работы функции: x = 2, y = 1. Это называется начальным условием цикла или предусловием, т. е. в начале цикла необходимо обеспечить выполнение этого условия и задать переменным нужные значения.
В последней строке напечатано: x = 5, y = 24. Для завершения работы нужно сделать еще один шаг, который в рекуррентной форме не показывается: x = 6, y = 120. Инвариант выполняется и в этом случае, в конце цикла он называется постусловием, т. е. условием, которое создастся после окончания цикла, или, другими словами, условием, которого имеют целью достигнуть с помощью цикла.
По постусловию можно определить условие окончания цикла. Это часть постусловия, которая позволяет определить, что цикл нужно закончить. В нашем случае условие окончания будет x = 6, или, в общем случае, x = n + 1, где n – число, для которого определяется факториал. Во многих языках программирования высокого уровня в формах записи цикла требуется указать не условие окончания, а условие продолжения цикла. В нашем случае цикл должен продолжаться до тех пор, пока x < 6 или x < n + 1.
Записав все условия (инвариант, предусловие, постусловие), можно сос-тавить тело цикла.
Очевидно, что для того чтобы приблизить условия окончания цикла, нужно увеличить x, например, на единицу. Обозначим x` = x + 1, где x` – значение переменной x на новом шаге. Нужно найти y` = (x` – 1)!. Мы не можем использовать функцию факториала, поскольку мы ее реализуем, но, используя определения факториала, и то, что y = (x – 1)!, получаем: y` = (x `– 1)! = (x + 1 – – 1)! = (x – 1)! x = y * x. Таким образом, можно получить значение y на новом шаге, умножив x на y из предыдущего шага. Получаем следующее тело цикла:
|
|
y=y*x;
x++;
Цикл разработан, осталось записать его на языке программирования. Запишем цикл с помощью изученного в первом семестре оператора for:
for(x=2, y=1; x<n+1; x++)
y=y*x;
В поле инициализации оператора мы записали инициализацию цикла – задание начальных значений переменных. Для того чтобы задать сразу два значения, был применен оператор «запятая», который указывает на то, что нужно выполнить последовательно два действия.
В операторе for во втором поле указывается условие выполнения цикла: цикл будет выполняться до тех пор, пока x < n, где n – число, факториал которого мы считаем.
Третье поле указывает шаг цикла, который выполняется после тела. Оператор x++ по смыслу соответствует шагу цикла, т. е. приближает условие окончания цикла, поэтому он был перенесен сюда из тела цикла.
Функция, вычисляющая факториал с помощью цикла, имеет вид:
int fact1(int n)
{
if(n==0) return 1;
if(n==1) return 1;
int x, y;
for(x=2, y=1; x<n+1;x++)
y=y*x;
return y;
}