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




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


В нашем случае это (sumall n) и (sumall (- n 1)).

Иногда просто найти это отношение, а если не получается надо выполнить следующую последовательность шагов.

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

b. Определить соотношение между парой этих функций.

Пример. Определим функцию power. Она берет два численных аргумента m и n вычисляет значение m в степени n.

(power 2 3) возвращает 8

Вначале составим рекурсивную таблицу.

Шаг 1. Завершение (Терминальная ветвь)
n=0 - аргумент
(power 2 0) = 1 - значение

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

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

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

    (power 5 3) =125 (power 5 2) = 25

    (power 3 1)=3 (power 3 0 )=1

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

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

    умножением на m

    (defun power (m n) (cond ((zerop n) 1) (t (* m (power m (- n 1))))))


    6.4 CDR рекурсия.

    Рассмотрена рекурсивная обработка чисел. Когда информация представлена в виде списка, то появляется необходимость рекурсивной обработки списков. Основная рекурсия над списками CDR рекурсия.

    Логика и структура СDR рекурсии сходна с численной рекурсией.

    Пример. Написать функцию list-sum

    которая берет один аргумент, список чисел, и возвращает сумму этих чисел.

    Последовательно упрощающимся аргументом в этом случае будет список. Упрощение списка (cdr lis). Последнее значение аргумента nil.

    Составим рекурсивную таблицу для (list-sum lis)

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

    (list-sum nil) = 0 - значение

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

    Рекурсивные отношения между

    (list-sum lis) и (list-sum (cdr lis))

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

    (list-sum '(2 5 3)) =10 (list-sum '(5 3)) = 8

    (list-sum '(3)) =3 (list-sum nil )=0

    2b. Характеристическое рекурсивное отношение (list-sum lis) может быть получена из
    (list-sum (cdr lis))

    сложением с (car lis).

    Текст функции.

    (defun list-sum (lis ) (cond ((null lis) 0) (t (+ (car lis) (list-sum (cdr lis))))))

    <




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