Программирование в среде Турбо Паскаль (Поляков, Круглов) - страница 80

и целой степени числа:

Видно, что для вычисления каждого последующего значения нужно знать предыдущее. В Паскале рекурсия записывается так же, как и в формулах. Для сравнения рассмотрим реализации функций вычисления того же факториала:

| >FUNCTION Fact( n : Word ) : Longlnt;

| BEGIN

| >if n=0

| >then Fact := 1

| >else Fact := n * Fact( n-1 );

| END;

и степени n числа x:

| >FUNCTION IntPower( x : Real; n : Word ) : Real;

| BEGIN

| >if n=0

| >then IntPower := 1

| >else IntPower := x * IntPower( x, n-1);

| END;

Если в функцию передаются n>0, то происходит следующее: запоминаются известные значения членов выражения в ветви ELSE (для факториала это n, для степени — x), а для вычисления неизвестных вызываются те же функции, но с «предшествующими»

- 123 -

аргументами. При этом вновь запоминаются (но в другом месте памяти!) известные значения членов и происходят вызовы. Так происходит до тех пор, пока выражение не станет полностью определенным (в наших примерах — это присваивание в ветви THEN), после чего алгоритм начинает «раскручиваться» в обратную сторону, изымая из памяти «отложенные» значения. Поскольку при этом на каждом очередном шаге все члены выражений уже будут известны, через n таких, «обратных» шагов мы получим конечный результат.

Необходимым для работоспособности рекурсивных процедур является наличие условия окончания рекурсивных вызовов (например, проверка значения изменяющегося параметра). Действия, связанные с такой проверкой, уже не могут содержать рекурсивных вызовов. Если это условие не будет выполняться, то глубина рекурсии станет бесконечной, что неизбежно приведет к аварийному останову программы.

Зачастую внесение рекурсивности в программы придает им изящность. Но всегда оно же «заставляет» программы расходовать больше памяти. Дело в том, что каждый «отложенный» вызов функции или процедуры — это свой набор значений всех локальных переменных этой функции, размещенных в стеке. Если будет, например, 100 рекурсивных вызовов функции, то в памяти должны разместиться 100 наборов локальных переменных этой функции. В Турбо Паскале размер стека (он регулируется первым параметром директивы компилятора $M) не может превышать 64К — а это не так уж много.

Несмотря на наглядность рекурсивных описаний, во многих случаях те же задачи более эффективно решаются итерационными методами, не требующими «лишней» памяти при сопоставимой скорости вычислений. Например, функция вычисления целой степени числа X может быть переписана следующим образом:

| FUNCTION IntPower(x : Real; n : Word ) : Real;