Рекурсии высших порядков

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

Пример

Выполняется «развертка» списка в один уровень. Так, список (a (b c) d (e (f)) g) должен быть «развернут» в список (a b c d e f g).

(sexpr unwrap (lambda (lst) (vsp lst nil)))

(sexpr vsp (lambda (isx rez)

(cond ((null isx) rez)

((atom isx)(cons isx rez))

(t (vsp (car isx)(vsp (cdr isx) rez)))

)

))

В данном примере в реализации 2-й функции применяется метод накапливающих параметров. Функция vsp программируется следующим образом. Необходимо присоединить головную часть списка к уже развернутой хвостовой части.

• Если головная часть пустой список,- значит результат уже вычислен

• Если 1-й аргумент (не список) атом, то необходимо присоединить его к хвостовой части списка (поскольку там находится развернутый список)

• Если 1-й аргумент является списком, то выполняется рекурсивный вызов функции vsp, причем в качестве 1-го аргумента ей передается голова списка и в качестве 2-го аргумента развернутая часть хвоста списка (что реализуется за счет повторного рекурсивного вызова функции)

В данном примере представлена рекурсия 1-го порядка.

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

Метод накапливающих параметров

Идея метода(та же что и в Прологе) состоит в том, что программируемая функция включает вспомогательную функцию в определении с «лишним параметром», в котором накапливается результат.

Пример

Перепишем функцию обращения списка invlist. следующим образом.

(sexpr invlist (lambda (x) (inv x nil)))

(sexpr inv (lambda (ISX REZ)

(cond ((null ISX) REZ)

(t (inv (cdr ISX)(cons (car ISX) REZ))))

))

inv – рекурсивна по значению.

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

Пример

Сортировка списка целых чисел.

(sexpr sort (lambda (x) (sortn x nil)))

(sexpr sortn (lambda (x y )

(cond ((null x) y)

(t (sortn (cdr x) ( ins (car x ) y))))

))

Самостоятельно дать определениефункцию ins (x,y), которая вставит элемент X в сортированный список Y в надлежащую, по условиям сортировки, позицию.

Функционалы

Аргумент, значением которого является функция, называют функциональным аргументом. Функцию с функциональными аргументами, которая интерпретирует эти аргументы как функции называют в функциональном программировании функционалом. Функциональными аргументами могут быть:

• символьное имя, сопоставленное определению функции,

• лямбда-выражение,

• т.н. «замыкание», являющееся внутренним прдставлением функции в Лиспе.

Функции и функционалы в качестве результата вычислений могут возвращать как функции (а вернее их внутренние представления в виде «замыканий»), так и символьные имена или списки, соответствующие по своей структуре лямбда-выражениям.

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

В дальнейшем для сокращения записи определений функций будем использовать форму defun, которая упрощает синтаксис определений, а семантически соответствует форме sexpr:

(sexpr символ (lambda (список символов) тело-функции) @

(defun символ (список символов) тело-функции)