Информатика: Сегментация программ. Гурьяшова Р.Н - 24 стр.

UptoLike

ВУЗ: 

ВГУВТ | Нижний Новгород

Составители: 

Рубрика: 

Принято считать рекурсивные программы более медленными за
счет дополнительных расходов на многократный вызов подпро-
граммы.
Пример
Числа Фибоначчи Fib(N) определяются следующим образом:
⎪
⎩
⎪
⎨
⎧
>−+−
=
=
=
.2если),2()1(
;2если,1
;1если,1
)(
NNFibNFib
N
N
NFib
Программа, BASIC Пояснения
N = 10
PRINT "N", "FIB(N) "
PRINT N, FIB(N)
END
FUNCTION FIB (N)
IF N = 1 OR N = 2 THEN
FIB = 1
ELSE
FIB = FIB(N - 1) + FIB(N - 2)
END IF
END FUNCTION
Функция FIB
Условие
останова
Рекурсивный
вызов
Результаты работы:
N FIB(N)
10 55
Не все языки допускают использование рекурсии; QBasic под-
держивает рекурсию, Фортран-77 – нет. В Фортране-9х для создания
рекурсивной процедуры необходимо описать ее как RECURSIVE, а в
случае функции – использовать для возврата значения имя, отличное
от имени функции (ключевое слово RESULT).
24
   Принято считать рекурсивные программы более медленными за
счет дополнительных расходов на многократный вызов подпро-
граммы.

   Пример
   Числа Фибоначчи Fib(N) определяются следующим образом:

                    ⎧1,                          если N = 1;
                    ⎪
         Fib( N ) = ⎨1,                          если N = 2;
                    ⎪ Fib( N − 1) + Fib( N − 2), если N > 2.
                    ⎩

                Программа, BASIC                     Пояснения
 N = 10
 PRINT "N", "FIB(N) "
 PRINT N, FIB(N)
 END

 FUNCTION FIB (N)                                 Функция FIB
    IF N = 1 OR N = 2 THEN                        Условие
       FIB = 1                                    останова
    ELSE
       FIB = FIB(N - 1) + FIB(N - 2)              Рекурсивный
    END IF                                        вызов
 END FUNCTION

   Результаты работы:

 N                FIB(N)
 10               55

    Не все языки допускают использование рекурсии; QBasic под-
держивает рекурсию, Фортран-77 – нет. В Фортране-9х для создания
рекурсивной процедуры необходимо описать ее как RECURSIVE, а в
случае функции – использовать для возврата значения имя, отличное
от имени функции (ключевое слово RESULT).



                               24

Страницы