Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=299070 Fri, 13 Feb 2004 22:08:53 +0000 Рекурсия https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=299070
[Нет. Есть одна тема, там где "фиксные выражения" в ней есть серьёзный пример с деревьями. Но без описания.]]]> KiRiK Pascal: Общие вопросы https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=278511 Sat, 10 Jan 2004 10:32:16 +0000 Рекурсия https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=278511 Главный минус - тормозА. Часто рекурсивные процедуры и функции работают ОЧЕНЬ медленно.
Для примера: вычисление чисел Фиббоначчи.
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.
]]> tserega Pascal: Общие вопросы https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=277047 Wed, 07 Jan 2004 21:10:52 +0000 Рекурсия https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=277047 Цитата
@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. если не нравится могу удалить :)
[Оставь, нравится %)]]]> lamachok Pascal: Общие вопросы https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=272594 Mon, 29 Dec 2003 14:24:00 +0000 Рекурсия https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=272594 Как устроены переменные паскаля" в которой детально изложен принцип выделения памяти под переменные, объяснено, как используется стек, и для чего он нужен в процедурах или функциях (в том числе и рекурсивных)]]> Some1 Pascal: Общие вопросы https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=271346 Sat, 27 Dec 2003 03:24:30 +0000 Рекурсия https://forum.sources.ru/index.php?showtopic=41657&view=findpost&p=271346 Рекурсия

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

При написании рекурсивных программ следует помнить, что при рекурсивном вызове процедурой самой себя или другой процедуры следует соблюдать определенные «правила предосторожности». Рекомендуется компилировать программу с директивой {$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;
]]> @Hgpeu Pascal: Общие вопросы