Оберон / Компонентный Паскаль / Вики

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
=====2.4 Рекурсия на примере факториала=====

====1. Понятие о рекурсии====

''Рекурсия'' это такая ''рекурсия'', которая в ''рекурсии'' подразумевает ''рекурсию'', которая продолжает вызывать ''рекурсию'', которая... ''Рекурсия'' — это обращение к себе. Причём, это обращение может быть настолько многоуровневым, что смотря на самую дальнюю точку — просто не видишь её конец. Очень не плохо показана идея ''рекурсии'' в фильме "Начало" с [[https://ru.wikipedia.org/wiki/%D0%94%D0%B8_%D0%9A%D0%B0%D0%BF%D1%80%D0%B8%D0%BE,_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4%D0%BE|Леонардо Ди Каприо]]. Если вы его не могли посмотреть, то ещё можно понять что такое ''рекурсия'' из детского не очень доброго стишка, но, возможно, как любят говорить киношники — "основанного на реальных событиях":

	У попа была собака. Он её любил.
	Она съела кусок мяса — он её убил.
	В землю закопал и на могиле написал:
		"У попа была собака. Он её любил.
		Она съела кусок мяса — он её убил.
		В землю закопал и на могиле написал:
			"У попа была собака....
	
И так до бесконечности. Несчастная собака... Несчастный поп...
Но такова жестокая суть рекурсии.


====2. Вычисление факториала====
	
Для расчёта [[https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB|факториала]] можно пойти родственным путём, что и в прошлом примере, но //рекурсивным// он уже не будет((Вообще, вычисление в настоящем случае факториала через [[https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F|рекурсию]] — довольно //неэффективный// алгоритм. Надо стараться искать обходные пути. Вообще с рекурсией надо быть очень внимательным, так как //неограниченная// рекурсия мгновенно вызовет переполнение стека. На этом принципе работают чуть ли не половина вирусов для **MS Windows**. Можно отдельно почитать статью с множеством технических подробностей на http://codenet.ru/.)). В **КП** рекурсия разрешена и выполняется процедурой при вызове самой себя (прямо или косвенно). Важно понимать, что серия рекурсивных вызовов никогда не закончится, если не установить ограничитель. При вычислении факториала таким ограничителем служит число, по отношению к которому вычисляется факториал. Очень важно помнить, что факториал растёт //чудовищно// быстро, и чтобы избежать ошибки переполнения, это число не должно быть большим. Ниже, пример рекурсивного вычисления факториала на **КП**.

  Hello11.odc

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

	IMPORT мВв := In,
		мЛог := Log;

	PROCEDURE Факт_Получ (пцФактор: INTEGER): INTEGER;
	BEGIN
		IF пцФактор = 1 THEN
			мЛог.String('Достигнуто дно  '); мЛог.Ln;
			RETURN 1
		ELSE
			мЛог.String('пцФактор='); мЛог.Int(пцФактор); мЛог.Ln;
			RETURN пцФактор * Факт_Получ(пцФактор - 1);
		END;
	END Факт_Получ;

	PROCEDURE Старт*;
		VAR
			цФактор: INTEGER; (* факториал *)
			цБаза: INTEGER; (* основание факториала *)

	BEGIN
		мЛог.String('Введите основание факториала: ');
		мВв.Open;
		мВв.Int(цБаза); мЛог.Ln;
		мЛог.String('BEGIN цБаза='); мЛог.Int(цБаза); мЛог.Ln;
		цФактор := Факт_Получ(цБаза);
		мЛог.String('f('); мЛог.Int(цБаза); мЛог.String(')= '); мЛог.Int(цФактор); мЛог.Ln;
	END Старт;

BEGIN
END TestHello11.

"6" выделить перед пуском!!!

^TestHello11.Старт 6 
</code>
   

Обратите внимание, что в этом примере можно было использовать только одну переменную для вычисления факториала, если бы вывод в ''мЛог.Int(цФактор)'' выполнялся через вызов ''мЛог.Int(Фактор_Получ(пцФактор))''. Соответственно, строку выше можно было бы удалить и отказаться от объявления переменной "пцФактор".

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

  компилируется "TestHello11"   220   0
  Введите основание факториала: 
  BEGIN цБаза= 6
  пцФактор= 6
  пцФактор= 5
  пцФактор= 4
  пцФактор= 3
  пцФактор= 2
  Достигнуто дно  
  f( 6)=  720
  
Как видно из вывода переменная ''цБаза'' с каждым вызовом действительно уменьшалась на "1", и это была настоящая ''рекурсия''. :-)