Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1110798), страница 11
Текст из файла (страница 11)
На каждом шагерекурсии к Res будет подсоединяться слева очередной отщепленный отсписка элемент, и по окончании обработки всех элементов в Res будетсформирован весь реверсированный список. Такое отщепление элементовсписка X и их подсоединение к накапливающему параметру Resреализует вспомогательная рекурсивная функция Rev от двух аргументов:исходного списка и накапливающего параметра.
Тогда задача основнойфункции ReverseA сводится к вызову Rev с начальным значениемнакапливающего параметра, равным пустому списку:(defun ReverseA (X) (Rev X NIL)(defun Rev (X Res) ; Res - накапливающий параметр(cond ((null X) Res) ;выдача перевёрнутого списка(T (Rev (cdr X)(cons (car X) Res)))))Отметим, что как и в прошлом примере с SumPr3, вспомогательнаяфункция Rev использует хвостовую рекурсию.Покажем на примере ход реверсирования списка, используя техникупереписывания вычисляемого выражения:0)1)2)3)4)5)6)7)(ReverseA: X=(A (B D) C))(Rev: X=(A (B D) C), Res=())(Rev: X=((B D) C), Res=(cons 'A ()))(Rev: X=((B D) C), Res=(A))(Rev: X=(C), Res=(cons '(B D) '(A)))(Rev: X=(C), Res=((B D) A))(Rev: X=(), Res=(cons 'C '((B D) A)))(Rev: X=(), Res=(C (B D) A))=> (C (B D) A)В отличие от функции Reverse, в данном случае перевёрнутый списокначинает формироваться сразу (в параметре Res), сформированная его53часть передаётся на следующий шаг рекурсии.
Количество обращений кфункции cons равно длине n списка Х. Таким образом, использованиенакапливающего параметра уменьшает сложность Reverse отквадратичной до линейной.Рассмотренный приём с накапливающим параметром может бытьиспользован для построения функции ReverseAll, реверсирующейзаданный список на всех его уровнях, например:(ReverseAll '(A (B D) C)) => (C (D B) A)Укажем сначала решение без накапливающего параметра,использованием функции append и параллельной рекурсии:с(defun ReverseAll (X)(cond ((atom X) X)(T(append (ReverseAll (cdr X))(cons (ReverseAll (car X)) NIL)))))Попутно заметим, что в последней строке можно переставить местамиобращения к функциям cons и ReverseAll.Очевидно, более эффективно решение с накапливающимпараметром, которое реализуют две взаимосвязанные функции:(defun RevDepth (X)(cond ((atom X) X)(T (RevBroad X NIL)) ))(defun RevBroad (Y Res)(cond ((null Y) Res)(T (RevBroad (cdr Y)(cons (RevDepth (car Y)) Res)))))Обработка исходного списка и его подсписков идёт в двух направлениях –вглубь функцией RevDepth, а вширь – RevBroad.
Эти две функциивзаимно рекурсивны, а в RevBroad дополнительно использована простаярекурсия. В теле функции RevDepth для обработки неатомарных X привызове RevBroad заводится накапливающий параметр (первоначальноравный пустому списку). В теле же функции RevBroad в этотнакапливающий параметр Res собираются (в обратном порядке)обработанные (реверсированные) элементы верхнего уровня списка Y.Покажем это на примере:0) (RevDepth: X=(A (B D) C))1) (RevBroad: Y=(A (B D) C), Res=NIL)2) (RevBroad: Y=((B D) C),Res=(cons (RevDepth: X=A) ()))543) (RevBroad: Y=((B D) C), Res=(cons 'A ()))4) (RevBroad: Y=((B D) C), Res=(A))5) (RevBroad: Y=(C),Res=(cons (RevDepth: X=(B D)) '(A)))6) (RevBroad: Y=(C),Res=(cons (RevBroad: Y=(B D), Res=()) '(A)))7) (RevBroad: Y=(C),Res=(cons (RevBroad: Y=(D),Res=(cons (RevDepth: X=B) ()))'(A)))8) (RevBroad: Y=(C),Res=(cons (RevBroad: Y=(D), Res=(cons 'B ()))'(A)))9) (RevBroad: Y=(C),Res=(cons (RevBroad: Y=(D), Res=(B))'(A)))10) (RevBroad: Y=(C),Res=(cons (RevBroad: Y=(),Res=(cons (RevDepth: X=D) '(B)))'(A)))11) (RevBroad: Y=(C),Res=(cons (RevBroad: Y=(), Res=(cons 'D '(B)))'(A)))12) (RevBroad: Y=(C),Res=(cons (RevBroad: Y=(), Res=(D B)) '(A)))13) (RevBroad: Y=(C), Res=(cons '(D B) '(A)))14) (RevBroad: Y=(C), Res=((D B) A))15) (RevBroad: Y=(), Res=(cons (RevDepth: X=C)'((D B) A)))16) (RevBroad: Y=(), Res=(cons 'C '((D B) A)))17) (RevBroad: Y=(), Res=(C (D B) A))=> (C (D B) A)2.5.
Рекурсия более высокого порядкаРассмотрим задачу выравнивания списка произвольной длины иглубины, т.е. удаления в нём всех внутренних скобок, без изменениясостава и порядка следования входящих в список атомов:(Flatten '((P (Q)) R (T))) => (P Q R T).Результатом функции Flatten является одноуровневый список атомов.55Решение этой задачи параллельной рекурсией можно получить,опираясь на рекурсивное определение S-выражения:(defun Flatten (X)(cond ((null X) NIL)((atom X) (cons X ()))(T (append (Flatten (car X))(Flatten (cdr X)) )) ))Отметим, что при объединении результатов рекурсивных вызововиспользуется функция append, а не cons, поскольку необходимосоединить в один список два списка атомов, уже выровненных врезультате рекурсивных обращений.
Чтобы это было возможно, обааргумента функции append должны быть списками, а значит, результатомFlatten всегда должен быть список. Поэтому во второй ветви функции,при обработке атома, он заключается в скобки. В то же время не должензаключаться в скобки пустой список (атом NIL) – для этого служит перваяветвь функции. Тем самым функция не сохраняет в результирующемсписке атомы NIL:(Flatten '((P NIL (Q)) R ()(T))) => (P Q R T).Продемонстрируем ход вычислений функции Flatten:0)1)2)3)4)5)6)(Flatten: X=((A(B))C))(append (Flatten: X=(A(B)))(Flatten: X=(C)))(append (append (Flatten: X=A)(Flatten: X=((B))))(Flatten: X=(C)))(append (append '(A) (Flatten: X=((B))))(Flatten: X=(C)))(append (append '(A)(append (Flatten: X=(B))(Flatten: X=())))(Flatten: X=(C)))(append (append '(A)(append (Flatten: X=(B))(Flatten: X=())))(Flatten: X=(C)))(append (append '(A)(append (append (Flatten: X=B)(Flatten: X=()))(Flatten: X=())))(Flatten: X=(C)))567)8)9)10)11)12)13)14)15)16)(append (append '(A)(append (append '(B)(Flatten: X=()))(Flatten: X=())))(Flatten: X=(C)))(append (append '(A)(append (append '(B) NIL)(Flatten: X=())))(Flatten: X=(C)))(append (append '(A)(append '(B) (Flatten: X=())))(Flatten: X=(C)))(append (append '(A) (append '(B) NIL))(Flatten: X=(C)))(append (append '(A) '(B)) (Flatten: X=(C)))(append '(A B) (Flatten: X=(C)))(append '(A B) (append (Flatten: X=C)(Flatten: X=())))(append '(A B) (append '(C) (Flatten: X=())))(append '(A B) (append '(C) NIL))(append '(A B) '(C))=> (A B C)Поскольку рассмотренная функция использует для выравниваниявысоко затратную функцию append, построим решение с накапливающимпараметром.
Оно включает две функции: основная функция FlattenAвызывает вспомогательную функцию Flat, устанавливая для неёначальное значение накапливающего параметра. Flat реализуетсобственно рекурсивный процесс выравнивания:(defun FlattenA (X) (Flat X nil))(defun Flat (Y Res) ) ;вспомогательная функция(cond((null Y)Res);Res - накапливающий параметр((atom Y)(cons Y Res))(T (Flat (car Y) (Flat (cdr Y) Res)) )))В ходе рекурсии Flat в параметре Res постепенно накапливаетрезультат, рассматривая три возможных случая.
Если Y – пустой список, тоRes не меняется. Если аргумент Y – атом, отличный от NIL, то оннепосредственно заносится в Res. Если же Y – неатомарное выражение(точечная пара), его можно рассматривать как бинарное дерево, и сначаларекурсивно выравнивается правое поддерево (полученное операцией cdr),при этом используется параметр Res:(Flat (cdr Y) Res).57Полученный результат (выровненное правое поддерево) используется какнакапливающий параметр для выравнивания левого поддерева(полученного операцией car): (Flat (car Y)(Flat(cdr Y) Res)).Именно такой порядок рекурсивных вызовов функции Flat обеспечиваетсохранение исходного порядка атомов в выровненном списке.В данном случае один рекурсивный вызов стоит внутри другогорекурсивного вызова, демонстрируя ещё один, более сложный видрекурсии – рекурсию более высокого порядка.
Точнее, Flat – это рекурсияпервого порядка, поскольку порядок отсчитывается по числу вложенныхрекурсивных вызовов.Покажем на примере вычисление функции FlattenA :0)1)2)3)(FlattenA: X=((A(B))C))(Flat: Y=((A(B))C), Res=())(Flat: Y=(A(B)), Res=(Flat: Y=(C), Res=()) )(Flat: Y=(A(B)), Res=(Flat: y=C,Res=(Flat: Y=(), Res=())))4) (Flat: Y=(A(B)), Res=(Flat: Y=C, Res=()) )5) (Flat: Y=(A(B)), Res=(C) )6) (Flat: Y=A, Res=(Flat: Y=((B)), Res=(C)) )7) (Flat: Y=A, Res=(Flat: Y=(B),Res=(Flat: Y=(), Res=(C)) ))8) (Flat: Y=A, Res=(Flat: Y=(B), Res=(C)) )9) (Flat: Y=A, Res=(Flat: Y=B,Res=(Flat: y=(), Res=(C))))10) (Flat: Y=A, Res=(Flat: Y=B, Res=(C)) ))11) (Flat: Y=A, Res=(B C))=> (A B C)Заметим, что по окончании обработки очередного подсписка и возврате напредыдущий уровень вложенности списка туда передаётся списокпараметр Res, в котором уже накоплены атомы обработанных подсписков.В отличие от функции Flatten, общее количество обращений коперации cons при работе функции FlattenA минимально, т.е.
равночислу атомов обработанного списочного выражения. При этом дляобработки одного и того же выражения потребовалось меньшее числошагов вычисления (11 против 16) и меньшее количество вложенныхфункциональных вызовов (3 против 5).В качестве ещё одного примера рекурсии более высокого порядкаприведём определение функции Collect, собирающей все различныеатомы в заданном списочном выражении:(collect '(A(S A D)((Z(S))X C))) => (A D Z S X C)58Результирующий список – список атомов без повторений, т.е.
множество.Как и в задаче выравнивания списка, Collect используетвспомогательную функцию с накапливающим параметром Res, нодобавление атома в Res происходит только в том случае, когда этогоатома там нет:(defun Collect (X) (Col X nil))(defun Col (Y Res) ;вспомогательная функция(cond ((null Y) Res)((atom Y) (cond ((member Y Res)Res)(T(cons Y Res))))(T (Col (car Y) (Col (cdr Y) Res)) ) ))2.6. Задачи на программирование рекурсииПростая рекурсия1. Составить функцию (RemoveLast L), удаляющую из спискапоследний элемент. Например:(RemoveLast '(A (S D) E (Q))) => (A (S D) E)2.
Определить функцию-предикат (OneLevel L), которая проверяет,является ли список-аргумент одноуровневым списком:(OneLevel '(A B C)) => T,(OneLevel '((A) B C)) => NIL3. Запрограммировать функцию (Bubl N A) с двумя вычисляемымиаргументами – числом N и атомом A. Функция строит список глубиныN; на самом глубоком уровне элементом списка является A, а налюбом другом уровне список состоит из одного элемента. Например:(Bubl 3 5)=>(((5))).4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
