Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1156449), страница 10
Текст из файла (страница 10)
В итоге задача решается простой рекурсией (вместопараллельной):(defun SumPr2 (X)(cond ((null X) (cons 0 1))(T (let ((Y (car X))(Z (SumPr2 (cdr X)))(cons (+ Y (car Z))(* Y (cdr Z))) ))))51При этом для обработки списка длины n потребуется nрекурсивных обращений, а также n+1 обращений к функции cons длясоздания точечных пар, соединяющих сумму и произведение чисел, и nрасщеплений этих пар функциями car и cdr.Можно ещё сократить вычисления, если строить итоговую точечнуюпару только один раз, по завершении подсчёта суммы и произведения, а ихзначения накапливать в специальных параметрах-аргументах.
Для этогопотребуется вспомогательная функция от трёх аргументов, назовем еёAccum. Эта функция выполняет рекурсивный процесс прохода повходному списку чисел X с соответствующим пересчётом суммы ипроизведения. Задача же основной функции SumPr3 – вызвать Accum,передав ей начальные значения её параметров:(defun SumPr3 (X) (Accum X 0 1))(defun Accum (X S P)(cond((null X) (cons S P));итоговая точечная пара(T (Accum (cdr X) (+ S (car X)) ;пересчёт(* P (car X)) )) ))Аргументы S и P рекурсивной функции Accum сохраняют промежуточныерезультаты вычислений, постепенно накапливая сумму и произведениечисел. Тем самым, используя два накапливающих параметра, удаётсяизбежать излишних рекурсивных вызовов и ненужных соединений ирасщеплений точечных пар.
Поскольку в Accum применяется хвостоваярекурсия, вычисления могут быть дополнительно оптимизированы лиспинтерпретатором.В качестве следующего примера использования накапливающегопараметра вновь рассмотрим функцию Reverse, переворачивающуюсвой список-аргумент:(Reverse '(A (B D) C)) => (C (B D) A).Предложенное ранее определение опиралось на функцию append:(defun Reverse (X)(cond ((null X) NIL)(T (append (Reverse (cdr X))(cons (car X) NIL) )) ))Оценим вычислительную сложность этого решения, учитывая числовызовов функции cons (это более затратная операция по сравнению с carи cdr). Если n – длина исходного списка, то требуется n вызововфункции append. В свою очередь append вызывает себя рекурсивно mраз (где m – длина её первого аргумента-списка), копируя элементы своегопервого аргумента с помощью операции cons:52(defun append(L1 L2)(cond ((null L1) L2)(T (cons (car L1)(append (cdr L1) L2)) )))После каждого рекурсивного вызова функции Reverse длина аргументадля append уменьшается; имеем таким образом n вызовов append сдлиной списка m, равной соответственно n-1, n-2, …, 1, 0.
Общее числовызовов cons: n+(n-1)+(n-2)+ …+1+0 = n(n+1)/2 = О(n2).Получающуюся квадратичную зависимость от длины nреверсируемого списка хотелось бы сократить до О(n), и этого можнодостичь при введении накапливающего параметра.Пусть в ходе вычислений накапливающий параметр Res сохраняетпромежуточный результат – часть перевёрнутого списка. На каждом шагерекурсии к 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
