Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 38 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
Раздел 2. Рекурсивные функции
Рекурсивные функции – это функции, в теле которых содержится вызов
самих себя. Обычно их используют в ситуациях, когда легко свести исходную
задачу к задаче того же вида, но с другими исходными данным, например,
уменьшение размерности задачи, переход в новую точку и пр.
Каждый новый вызов рекурсивной функции предполагает сохранение со-
стояния всех переменных функции в специальной области памяти, называе-
мой стеком. После выполнения рекурсивной функции, управление передается
оператору, следующему за ее вызовом. При этом состояние всех переменных
восстанавливается из стека. Поэтому применение таких функций считается
очень затратным с точки зрения памяти и не подходит для решения задач
большой размерности. Тем не менее, существует множество задач, в которых
рекурсивные алгоритмы более просты и дают компактные программы.
Следует помнить, что любая рекурсивная функция должна иметь обяза-
тельное условие выхода из рекурсии. При выполнении этого условия управле-
ние передается в место предыдущей рекурсивной итерации, откуда произо-
шел рекурсивный вызов или в вызывающую функцию.
Далее приводится описание процесса решения некоторых задач с при-
менением рекурсивных функций.
Задача 1. Вычислить n! .
Когда рекурсия заключается в сведении к задаче меньшей размерности,
алгоритм аналогичен обратному ходу метода математической индукции.
Очевидно, что n!=n*(n-1)! Эта формула и определяет основное рекуррент-
ное соотношение – (n-1)! вычисляется с помощью вызова функции с фактиче-
ским параметром, принимающим значение n-1. Условие выхода из рекурсии –
это сведение задачи к тривиальному случаю – 1!=1, 0!=1.
# include <stdio.h>
// прототип функции вычисления факториала
long int Factorial(int n);
void main(void)
{
int n;
38
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                    .


                                          Раздел 2. Рекурсивные функции


    Рекурсивные функции – это функции, в теле которых содержится вызов
самих себя. Обычно их используют в ситуациях, когда легко свести исходную
задачу к задаче того же вида, но с другими исходными данным, например,
уменьшение размерности задачи, переход в новую точку и пр.
    Каждый новый вызов рекурсивной функции предполагает сохранение со-
стояния всех переменных функции в специальной области памяти, называе-
мой стеком. После выполнения рекурсивной функции, управление передается
оператору, следующему за ее вызовом. При этом состояние всех переменных
восстанавливается из стека. Поэтому применение таких функций считается
очень затратным с точки зрения памяти и не подходит для решения задач
большой размерности. Тем не менее, существует множество задач, в которых
рекурсивные алгоритмы более просты и дают компактные программы.
    Следует помнить, что любая рекурсивная функция должна иметь обяза-
тельное условие выхода из рекурсии. При выполнении этого условия управле-
ние передается в место предыдущей рекурсивной итерации, откуда произо-
шел рекурсивный вызов или в вызывающую функцию.

    Далее приводится описание процесса решения некоторых задач с при-
менением рекурсивных функций.
    Задача 1. Вычислить n! .
    Когда рекурсия заключается в сведении к задаче меньшей размерности,
алгоритм аналогичен обратному ходу метода математической индукции.
    Очевидно, что n!=n*(n-1)! Эта формула и определяет основное рекуррент-
ное соотношение – (n-1)! вычисляется с помощью вызова функции с фактиче-
ским параметром, принимающим значение n-1. Условие выхода из рекурсии –
это сведение задачи к тривиальному случаю – 1!=1, 0!=1.
    # include 

    // прототип функции вычисления факториала
    long int Factorial(int n);

    void main(void)
    {
          int n;

                                            38

Страницы