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




Рекурсия


ЛЕКЦИЯ 6.

РЕКУРСИЯ.


6. Р Е К У Р С И Я

Функция является рекурсивной, если в ее определении содержится вызов самой этой функции.

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

ПРИМЕР.

Определим функцию MEMBER

(defun MEMBER (item list)

(cond ((null list) nil)

((eql (car list) item) list)

(t (MEMBER item (cdr list)))))


6.1 Численная рекурсия

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

Например (sumall 9) должно вернуть 45

Это можно решить циклически; мы решим рекурсивно.

Отметим два факта:

1. Если n=0, сумма чисел между 0 и n равна 0.

2. Если n>0, сумма чисел между 0 и n

равна n плюс сумма чисел между 0 и n-1.

Эти два факта переводятся непосредственно в определение функции:

(defun sumall (n)

(cond ((zerop n) 0)

(t (+ n (sumall (- n 1))))))

Производится проверка n : равно нулю или нет.

Если значение n=0, то функция возвращает 0 .

В противном случае , функция вызывает сама себя для вычисления суммы чисел между 0 и n-1 и и добавляет n к этой сумме.


6.2 Как работает рекурсивная функция.

Посмотрим как работает рекурсивная функция. Проследим за несколькими вызовами.

Как работает (sumall 0) все ясно. Функция возвращает 0.

Эта ветвь в cond называется терминальной (terminating) завершающей, так как функция дает значение без рекурсивного вызова.

Если (sumall 1), то идет расчет по второй ветке,

которая называется рекурсивной, так как идет вызов самой себя.

В этом случае (+ 1 (sumall 0) и значение 1.

Если (sumall 2) , то по рекурсивной ветке (+ 2 (sumall 1)) и возвращает 3.

Если посмотреть,

(sumall 3) вызывает (sumall 2)

(sumall 1) вызывает (sumall 0).

После того как (sumall 0) вернет 0,

(sumall 1) вернет 1,

(sumall 2) вернет 3,

(sumall 3) это вызов верхнего уровня даст значение 6.




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