
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.97.9.170] |
![]() |
|
Сообщ.
#1
,
|
|
|
Рекурсия
Подпрограмма называется рекурсивной, если она вызывает саму себя (прямая рекурсия). Рекурсивной также будет процедура, вызывающая другую процедуру, которая, в свою очередь, обращается к первой процедуре (косвенная рекурсия). Возможны и более сложные конструкции. При написании рекурсивных программ следует помнить, что при рекурсивном вызове процедурой самой себя или другой процедуры следует соблюдать определенные «правила предосторожности». Рекомендуется компилировать программу с директивой {$S+}. Эта директива включает проверку переполнения стека (области памяти, в которой хранится состояние вызывающей подпрограммы). Если в процессе выполнения программы происходит переполнение стека, вызов процедуры или функции, откомпилированной с опцией {$S+}, приводит к завершению работы программы, а на дисплей выдается сообщение об ошибке. Полезно также использовать директиву {$R+}, включающую проверку диапазона переменных. В начале каждой процедуры (функции), вызываемой рекурсивно, можно разместить строку ![]() ![]() if keypressed then Halt Количество рекурсивных вызовов называется глубиной рекурсии. Глубина рекурсии должна быть конечной. Позаботиться об этом должен программист, выбирающий или разрабатывающий рекурсивный алгоритм. Признаком использования рекурсии является возможность разбиения задачи на две части: простую и примитивную. Простая задача должна быть сходной по решению с общей задачей. Рассмотрим классический пример: «необходимо найти факториал числа» (факториал: y=n! = 1*2*3*4*…*n) 1!=1 2!=1*2=1!*2 3!=1*2*3=2!*3 n!=(n-1)!*n ![]() ![]() function f(n: longint): longint; begin if n=1 then f:=1 else f:=f(n-1)*n; end; |
Сообщ.
#2
,
|
|
|
Если вы не понимаете, но хотите знать, почему важно использовать директиву {$S+} (слежение за переполнением стека), то читайте тему "Как устроены переменные паскаля" в которой детально изложен принцип выделения памяти под переменные, объяснено, как используется стек, и для чего он нужен в процедурах или функциях (в том числе и рекурсивных)
|
Сообщ.
#3
,
|
|
|
Цитата @Hgpeu, 27.12.03, 04:24 также будет процедура, вызывающая другую процедуру, которая, в свою очередь, обращается к первой процедуре (косвенная рекурсия). При этом нарушаются правила Паскаля, т.к. вышестоящая подпрограмма не знает о существовании нижестоящей. Для того, что бы всё работало тип-топ, надо использовать опережающее описание. Например: Цитата Procedure b(i:integer);Forward; Procedure a(j:integer); begin b(i) end; Procedure b(i:integer); begin a(j); end; P.S. если не нравится могу удалить ![]() [Оставь, нравится %)] |
Сообщ.
#4
,
|
|
|
В чем плюсы и минусы рекурсии?
Главный минус - тормозА. Часто рекурсивные процедуры и функции работают ОЧЕНЬ медленно. Для примера: вычисление чисел Фиббоначчи. F(0) = F(1) = 1, F(N) = F(N - 1) + F(N - 2), N >= 2 Очевидное рекурсивное решение: ![]() ![]() Function Fib(N : Byte) : Longint; Begin If (N = 0) Or (N = 1) Then Fib:=1 Else Fib:=Fib(N - 1) + Fib(N - 2); End; Вычисление Fib(20) занимает очень много времени, т.к. многие значения функции пересчитываются по многу раз. Построим "дерево" вычислений Fib(5). ![]() ![]() Fib(5) Fib(4) Fib(3) Fib(2) Fib(3) Fib(2) Fib(1) Fib(1) Fib(0) Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0) Можно заметить, что Fib(2) вычисляется 3 раза! Для вычисления Fib(5) потребовалось 16 рекурсивных вызовов. В общем случае число вызовов Fib(N) пропорционально 2^N. Плюсы - легкое программирование рекурентных формул и алгоритмов. Рассмотрим пример: сгенерировать все подмножества данного множества. Пусть есть N предметов, каждый из которых можно взять, или не взять. Значит, число вариантов 2^N. Решение может быть таким: ![]() ![]() Var N : Longint; {Число предметов} Procedure Solve(S : String; P : Longint); {S - текущий комплект, P - номер предмета,который рассматриваем} Begin If (P > N) Then {если проверили все N предметов} Writeln(S) Else {выводим на экран: 0 - предмета нет, 1 - есть} Begin Solve(S + '1', P + 1); {можем взять очередной предмет} Solve(S + '0', P + 1); {а можем не взять} End; End; Begin N:=3; Solve('', 1); End. |
Сообщ.
#5
,
|
|
|
К плюсам также можно отнести и то, что рекурсия - единственно возможный способ программирования деревьев (конечно можно извращаться - эммулировать стэк и т.д. но это мы не считаем). Про деревья см. соответствующие раздел (если он есть, в чем я пока не уверен).
[Нет. Есть одна тема, там где "фиксные выражения" в ней есть серьёзный пример с деревьями. Но без описания.] |