Инструменты пользователя

Инструменты сайта


bb:redbook:204

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

bb:redbook:204 [2017/08/30 09:52]
prospero78 [2. Вычисление факториала]
bb:redbook:204 [2018/11/30 01:13]
Строка 1: Строка 1:
-=====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", и это была настоящая ''рекурсия''. :-) 
- 
-====3. Примечания==== 
-  
-Вообще, вычисление в настоящем случае факториала через [[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/. 
  
bb/redbook/204.txt · Последнее изменение: 2020/10/29 07:08 (внешнее изменение)