Функциональное программирование




Рекурсия - часть 2



6.2.1 Трасса.


6.2.2 Правила записи рекурсивной функции.

Этот простой случай иллюстрирует несколько

правил в записи рекурсивной функции.

1. Терминальная ветвь необходима для окончания вызова. Без терминальной ветви рекурсивный вызов был бы бесконечным. Терминальная ветвь возвращает результат, который является базой для вычисления результатов рекурсивных вызовов.
2. После каждого вызова функцией самой себя, мы должны приближаться к терминальной ветви. В нашем случае вызовы уменьшали n и и была гарантия, что на некотором шаге будет вызов (sumall 0). Всегда должна быть уверенность, что рекурсивные вызовы ведут к терминальной ветви.

3. Проследить вычисления в рекурсии чрезвычайно сложно. Очень трудно мысленно проследить за действием рекурсивных функций. Это практически невозможно для функций более сложных, чем sumall.

Таким образом мы должны уметь писать рекурсивные функции, без того чтобы представлять точно порядок вычисления.


Как писать рекурсивные функции.

При написании рекурсивных функций мы должны планировать терминальные и рекурсивные ветви.

Таблица. Рекурсивная функция SUMALL

Шаг 1. Завершение (Терминальная ветвь)

n=0 - аргумент

(sumall 0) = 0 - значение

  • Шаг 2. Рекурсивная ветвь

    Рекурсивные отношения между (sumall n) и (sumall(- n 1 )

    2а. Примеры рекурсии

    (sumall n)

    (sumall(- n 1)

    (sumall 5)=15

    (sumall 4)=10

    (sumall 1)=1

    (sumall 0)=0

    2b. Характеристическое рекурсивное отношение

    (sumall n) может быть получена из (sumall (- n 1)

    прибавлением N

    1. Планирование терминальной ветви.

    При написании рекурсивной функции мы должны решить, когда функция может вернуть значение без рекурсивного вызова.

    2. Планирование рекурсивной ветви.

    В этом случае мы вызываем функцию рекурсивно с упрощенным аргументом и используем результат для расчета значения при текущем аргументе.

    Таким образом мы должны решить:

    1. Как упрощать аргумент, приближая его шаг за шагом к конечному значению.

    2. Кроме этого необходимо построить форму, называемую рекурсивным отношением, которая связывает правильное значение текущего вызова со значением рекурсивного вызова.




    Содержание  Назад  Вперед