Компонентный Паскаль/Рекурсия на примере факториала

Рекурсия на примере факториала

---

Понятие о рекурсии

Рекурсия это такая рекурсия, которая в рекурсии подразумевает рекурсию, которая продолжает вызывать рекурсию, которая... Рекурсия -- это обращение к себе. Причём, это обращение может быть настолько многоуровневым, что смотря на самую дальнюю точку -- просто не видишь её конец. Очень не плохо показана идея рекурсии в фильме "Начало" с Леонардо Ди Каприо. Если вы его не могли посмотреть, то ещё можно понять что такое рекурсия из детского не очень доброго стишка, но, возможно, как любят говорить киношники -- "основанного на реальных событиях":

У попа была собака. Он её любил.
Она съела кусок мяса -- он её убил.
В землю закопал и на могиле написал:
"У попа была собака. Он её любил.
Она съела кусок мяса -- он её убил.
В землю закопал и на могиле написал:
У попа была собака....

И так до бесконечности. Несчастная собака... Несчастный поп...

Но такова суть рекурсии.

Вычисление факториала

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

Hello11.odc

MODULE TestHello11;
	(* это программа на языке
	Компонентный Паскаль. Она показывает
	как можно вычислить произвольный факториал рекурсией. *)

	IMPORT In, Log, Math;

	PROCEDURE GetFactorial (n: INTEGER): INTEGER;
	BEGIN
		IF n = 1 THEN
			Log.String('Достигнуто дно  '); Log.Ln;
			RETURN 1
		ELSE
			Log.String('n='); Log.Int(n); Log.Ln;
			RETURN n * GetFactorial(n - 1);
		END;
	END GetFactorial;

	PROCEDURE Start*;
		VAR
			f: INTEGER; (* факториал *)
			n: INTEGER; (* основание факториала *)

	BEGIN
		Log.String('Введите основание факториала: ');
		In.Open;
		In.Int(n); Log.Ln;
		Log.String('BEGIN n='); Log.Int(n); Log.Ln;
		f := GetFactorial(n);
		Log.String('f('); Log.Int(n); Log.String(')= '); Log.Int(f); Log.Ln;
	END Start;

BEGIN
END TestHello11.

Обратите внимание, что в этом примере можно было использовать только одну переменную для вычисления факториала, если бы вывод в "Log.Int(f)" выполнялся через вызов "Log.Int(GetFactorial(n))". Соответственно, строку выше можно было бы удалить и отказаться от объявления переменной "f".

Вывод программы представлен ниже:

компилируется "TestHello11"   220   0
Введите основание факториала: 
BEGIN n= 6
n= 6
n= 5
n= 4
n= 3
n= 2
Достигнуто дно  
f( 6) =  720

Как видно из вывода переменная "n" с каждым вызовом действительно уменьшалась на "1", и это была настоящая рекурсия. )