Рекурсивная схема организации вычислительного процесса

Общая схема рекурсивного вычислительного процесса представлена на рис. 6.

вход

принятие решения

о завершении

нет

сохранение фрейма активации

промежуточные вычисления

окончательные вычисления

восстановление фрейма активации

выход

Обращение метода к самому себе

да

Рис. 6. Схема рекурсивного вычислительного процесса

Так как обращаться к рекурсивному методу можно как из него самого, так и извне, каждое обращение к рекурсивному методу вызывает его независимую активацию. При каждой активации образуются копии всех локальных переменных и формальных параметров рекурсивного метода, в которых “оставляют следы” операторы текущей активации. Таким образом, для рекурсивного метода может одновременно существовать несколько активаций. Для обеспечения правильного функционирования рекурсивного метоода необходимо сохранять адреса возврата в таком порядке, чтобы возврат после завершения каждой текущей активации выполнялся в точку, соответствующую оператору, непосредственно следующему за оператором рекурсивного вызова. Совокупность локальных переменных, значений фактических параметров, подставляемых на место формальных параметров рекурсивного метода, и адреса возврата однозначно характеризует текущую активацию и образует фрейм активации. Фрейм активации необходимо сохранять при очередной активации и восстанавливать после завершения текущей активации.

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

В основе рекурсивного вычислительного процесса лежит рекурсивный цикл, который реализуется через вызов рекурсивного метода, причем каждая активация рекурсивного метода эквивалентна одному проходу итеративного цикла While.

Общая схема рекурсивного цикла:

[спецификаторы] тип Recursion_Cycle (…)

{

if < условие цикла >

{

< тело рекурсивного цикла; >

Recursion Cycle (…);

}

}

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

Общая схема бесконечного рекурсивного цикла:

[спецификаторы] тип Infinite Recursion_Cycle (…)

{

if < условие цикла >

{

Infinite Recursion_Cycle (…);

< тело рекурсивного цикла; >

}

}

Рекурсивная схема вычисления факториала:

Базисная часть:

0! = 1; 1! = 1;

Рекурсивная часть:

N! = N * ( N-1 )! = N * ( N-1 ) * ( N-2 )! = N * ( N-1 ) * … * ( N – ( N-1 ) )! =

Промежуточные вычисления и обращения метода к самому себе

= N * ( N-1 ) * ( N-2) * . . . * 2 *

1! Базисная часть 1!=1

. . . вычисления

Окончательные вычисления

Метод, реализующий рекурсивную схему вычисления факториала:

using System;
namespace Recursion
{
class Recursion
{
public static long Recurs_fact( int n )
{
long f;
if ( n == 0 || n == 1)		// принятие решения о завершении вычислений:
f = 1;	// да – окончательные вычисления для базисной части
else
{
f = Recurs_fact ( n-1);			// нет – промежуточные вычисления и обращение метода к самому себе
f = f * n;	// окончательные вычисления для рекурсивной части { 1 }
}
return f;
}				// { 2 }
static void Main()
{
Console.Write( “Введите целое число: “ );
int x = int.Parse( Console.ReadLine() );
long y = Recurs_fact( x );
Console.WriteLine( “Рекурсивный факториал = {0}”, y );
}
}
}

{ 1 } – адрес возврата после завершения активации,

{ 2 } – завершение активации.

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

Другой характеристикой рекурсивного метода является глубина рекурсии, определяемая максимальным уровнем рекурсии в процессе вычисления при заданных аргументах. В общем случае эта величина неочевидна, исключение составляют простые рекурсивные методы, например, при вычислении значения N! глубина рекурсии равна N.

Так как при выходе из текущей активации самым первым должен быть восстановлен фрейм, который был позже всех сохранен, для хранения фреймов используется автоматическая память, т.е. область системного стека ([10]: с.31). Таблица 1 и рис. 7 поясняют механизм рекурсивных вычислений.

Таблица 1.