На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила ЧаВо (FAQ) разделов Паскаля
В этом разделе разрешено создавать только темы, в которых описано РЕШЕНИЕ какой-либо общей проблемы, или описание какого-либо аспекта языка Паскаль.
Обсуждение уже созданных тем разрешено, но только конструктивное, например указание на ошибку или уточнение имеющегося текста.

Также читать Требования к оформлению статей
Модераторы: volvo877, Romtek
  
> Рекурсия , или подпрограмма, вызывающая саму себя
    Рекурсия

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

    При написании рекурсивных программ следует помнить, что при рекурсивном вызове процедурой самой себя или другой процедуры следует соблюдать определенные «правила предосторожности». Рекомендуется компилировать программу с директивой {$S+}. Эта директива включает проверку переполнения стека (области памяти, в которой хранится состояние вызывающей подпрограммы). Если в процессе выполнения программы происходит переполнение стека, вызов процедуры или функции, откомпилированной с опцией {$S+}, приводит к завершению работы программы, а на дисплей выдается сообщение об ошибке. Полезно также использовать директиву {$R+}, включающую проверку диапазона переменных. В начале каждой процедуры (функции), вызываемой рекурсивно, можно разместить строку
    ExpandedWrap disabled
      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

    ExpandedWrap disabled
      function f(n: longint): longint;
      begin
        if n=1 then f:=1
        else f:=f(n-1)*n;
      end;
      Если вы не понимаете, но хотите знать, почему важно использовать директиву {$S+} (слежение за переполнением стека), то читайте тему "Как устроены переменные паскаля" в которой детально изложен принцип выделения памяти под переменные, объяснено, как используется стек, и для чего он нужен в процедурах или функциях (в том числе и рекурсивных)
        Цитата
        @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. если не нравится могу удалить :)
        [Оставь, нравится %)]
        Сообщение отредактировано: Song -
          В чем плюсы и минусы рекурсии?
          Главный минус - тормозА. Часто рекурсивные процедуры и функции работают ОЧЕНЬ медленно.
          Для примера: вычисление чисел Фиббоначчи.
          F(0) = F(1) = 1, F(N) = F(N - 1) + F(N - 2), N >= 2
          Очевидное рекурсивное решение:
          ExpandedWrap disabled
            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).
          ExpandedWrap disabled
                                            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.
          Решение может быть таким:
          ExpandedWrap disabled
            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.
            К плюсам также можно отнести и то, что рекурсия - единственно возможный способ программирования деревьев (конечно можно извращаться - эммулировать стэк и т.д. но это мы не считаем). Про деревья см. соответствующие раздел (если он есть, в чем я пока не уверен).

            [Нет. Есть одна тема, там где "фиксные выражения" в ней есть серьёзный пример с деревьями. Но без описания.]
            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script execution time: 0,0310 ]   [ 16 queries used ]   [ Generated: 30.05.24, 21:53 GMT ]