Рекурсивная обработка линейных списков 1 Структуры и алгоритмы обработки данных, 1 Лекция 2 Раздел: Рекурсивная обработка списков Тема Лекции: Рекурсивная обработка линейных списков

Рекурсивная обработка линейных списков 2 Литература Основная Алексеев А. Ю., Ивановский С. А., Куликов Д. В. Динамические структуры данных: Учеб. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», (с. 20) Дополнительная Алагич С., Арбиб М. Проектирование корректных структурированных программ. М.: Радио и связь, Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2 ч.- М.:Мир, Фостер Дж. Обработка списков. М.: Мир, 1974

Рекурсивная обработка линейных списков 3 Учебный курс МТИ Абельсон Х., Сассман Д.Д., Сассман Д. Структура и интерпретация компьютерных программ – М.: Добросвет, КДУ, 2006 Массачу́сетсский технологи́ческий институ́т (англ. Massachusetts Institute of Technology, MIT) университет и исследовательский центр, расположенный в Кембридже (шт. Массачусетс, США). Иногда также упоминается как Массачусетсский институт технологий и Массачусетсский технологический университет.англ.университетисследовательский центрКембриджеМассачусетсСША

Рекурсивная обработка линейных списков 4 «Хвост» списка «Голова» списка Модельное представление линейного списка Скобочная запись: x = (a b c d e) или [a, b, c, d, e] или (a; b ; c ; d ; e) Функции-селекторы: «голова» - head, first «хвост» - tail, rest применяются к непустому списку и позволяют разобрать его на составные части. Например, Head(x) = a, Tail(x) = (b c d e), Head( Tail(x) ) = b, Tail( Tail(x) ) = (c d e)

Рекурсивная обработка линейных списков 5 Функция-конструктор Cons (x, y) x = a - элемент базового типа, y = (b c d e) - список Cons(x, y) = (a b c d e) Свойства: Cons( Head(z), Tail(z)) = z Head(Cons(x, y)) = x Tail(Cons(x, y)) = y

Рекурсивная обработка линейных списков 6 Иллюстрация Cons( Head(z), Tail(z)) = z Head(z) z Tail(z) Cons( Head(z), Tail(z) ) = z

Рекурсивная обработка линейных списков 7 Функция-конструктор Cons(x, y) Пустой список: ( ) или Nil Cons(a, Nil) = Cons(a, ( )) = (a) (a b c d e) = Cons(a, Cons(b, Cons(c, Cons(d, Cons(e, Nil))))) Это «операционное» представление списка (формальное определение скобочного представления - далее) Функция-индикатор: Null(z) Null(Nil) = true, z = (a b c d e) Null(z) = false Всегда Null(Cons(x, y)) = false

Рекурсивная обработка линейных списков 8 Примеры Пример 1.1. Функция Size, вычисляющая число элементов (длину) списка. ySize(y) (d c b a)4 (f)(f)1 Nil0 Случай 1: y = NilSize(y) = 0 Случай 2: y Nil пусть Size(Tail(y)) = n, тогда Size(y) = n + 1. Рекурсивная функция Size(y) = if Null(y) then 0 else Size(Tail(y)) + 1.

Рекурсивная обработка линейных списков 9 Примеры Пример 1.2. Функция Sum, вычисляющая сумму элементов числового списка. ySum(y) ( )15 (-7 7)0 Nil0 Случай 1: y = NilSum(y) = 0 Случай 2: y Nil пусть Sum(Tail(y)) = s, тогда Sum(y) = Head(y) + s. Рекурсивная функция Sum(y) = if Null(y) then 0 else Head(y) + Sum(Tail(y)).

Рекурсивная обработка линейных списков 10 Пример 1.3. Число вхождений Numb(x, y) элемента x в список y xyNumb(x, y) b(a b c d)1 a(a b b a)2 e 0 aNil0 Случай 1: y = Nil Numb( x, y) = 0 Случай 2: y Nilпусть Numb(x, Tail(y)) = n, тогда подслучай 2.1: x = Head(y) Numb( x, y) = n + 1 подслучай 2.2: x Head(y) Numb( x, y) = n Рекурсивная функция Numb( x, y) = if Null(y) then 0 else if x = Head(y) then Numb(x, Tail(y)) + 1 else Numb(x, Tail(y))

Рекурсивная обработка линейных списков 11 Пример 1.4. Функция Concat, соединяющая два списка в один. Например, Concat(y, z) = (a b c d) для y = (a b) и z = (c d). Случай 1: y = Nil Concat(y, z) = z Случай 2: z = Nil Concat(y, z) = y Случай 3: y Nil и z Nil пусть Concat(Tail(y), z) = u, тогда Concat(y, z) = Cons(Head(y), u) y z Head(y) Tail(y) Concat(Tail(y), z) = u

Рекурсивная обработка линейных списков 12 Пример Concat((a b), (c d)) = Cons(a, Concat((b), (c d))). Concat((b), (c d)) = Cons(b, Concat(Nil, (c d))). Concat(Nil, (c d)) = (c d). Concat((b), (c d)) = Cons(b, (c d)) = (b c d). Concat((a b), (c d)) = Cons(a, (b c d)) = (a b c d). Замечания: 1. Список y разбирается и затем собирается даже если список z пуст. 2. Функция Cons вызывается Size(y) раз. Рекурсивная функция Concat(y, z) = if Null(y) then z else Cons(Head(y), Concat(Tail(y), z)).

Рекурсивная обработка линейных списков 13 Разборка и сборка при выполнении функции Concat(y, z) … y z

Рекурсивная обработка линейных списков 14 Пример 1.5. Функция Append, добавляющая элемент x в конец списка y. Например, Append(y, x) = (a b c) для y = (a b) и x = c. Append(y, x) = Concat(y, Cons(x, Nil)). Пример 1.6. Функция Reverse, обращающая список. Например, Reverse((a b c)) = (c b a). Reverse(y) = if Null(y) then Nil else Concat (Reverse(Tail(y)), Cons(Head(y), Nil)). Head(y) Reverse(Tail(y)) Tail(y)

Рекурсивная обработка линейных списков 15 Вызовы Возвращаемые значения Reverse( (a b) ) Concat( Reverse(( b )),Cons( a, Nil )) * Reverse( (b) ) Concat(Reverse( Nil ),Cons( b, Nil )) * Reverse( Nil ) * Cons( b,Nil ) * Cons( a,Nil ) Cons( b, Concat( Nil, (a) ) ) * Concat( Nil, (a) ) ( b a ) ( b ) Nil ( b ) ( a ) (b a ) ( a )

Рекурсивная обработка линейных списков 16 Сложность функции Reverse (начало) Concat(y, z) = if Null(y) then z else Cons(Head(y), Concat(Tail(y), z)). Количество вызовов C(n) функции Cons в Concat, где n = Size(y) C(n) = C(n 1) + 1; C(0) = 0 C(n) = n

Рекурсивная обработка линейных списков 17 Сложность функции Reverse (продолжение) Reverse(y) = if Null(y) then Nil else Concat (Reverse(Tail(y)), Cons(Head(y), Nil) ). Количество вызовов R(n) функции Cons в Reverse R(n) = R(n 1) C(n 1) ; R(0) = 0 R(n) = R(n 1) (n 1) = R(n 1) + n; Метод итераций: R(n) = R(n 1) + n = R(n 2) + (n 1) +n = = R(n 3) + (n 2) + (n 1) +n = … R(n) = n + (n 1) + (n 2)+… = n(n + 1)/2 Итак, R(n) = n(n + 1)/2

Рекурсивная обработка линейных списков 18 Отступление (напоминание): Накапливающие параметры в рекурсивных подпрограммах fact (n) if n = 0 then 1 else fact (n 1) n fact (4) = fact (3) 4 fact (3) = fact (2) 3 fact (2) = fact (1) 2 fact (1) = fact (0) 1 = 1 1=1 fact (2) = fact (1) 2 = 1 2 = 2 fact (3) = fact (2) 3 = 2 3 = 6 fact (4) = fact (3) 4 = 6 4 = 24

Рекурсивная обработка линейных списков 19 Накапливающие параметры Рассмотрим вспомогательную функцию двух аргументов fct(n,m): fct(n,m) if n = 0 then m else fct(n 1,m n); Тогда fact(n) fct(n,1). m – накапливающий параметр fact(4) fct(4,1) = fct(3,4) = fct(2,3*4) = fct(1,2*12) = fct(0,24) =24 Замечание о стеке и хвостовой рекурсии. (см. след. слайды)

Рекурсивная обработка линейных списков 20 Замечание 1. Все умножения производятся при вычислении fct(n,m) по ходу прокладки трассы. Замечание 2. Вспомнить рекурсивное вычисление чисел Фибоначчи Представление и обработка структурированных данных: Практикум по программированию / С. А. Ивановский, В. А. Калмычков, А. А. Лисс, В. П. Самойленко. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», с.

Рекурсивная обработка линейных списков 21 Рекурсивный алгоритм и вычислительные процессы Замечание о стеке и хвостовой рекурсии. Рекурсивный алгоритм Стек хранит всю «предысторию» (трассу) Рекурсивный ВП Текущее состояние определяется параметрами Итеративный ВП

Рекурсивная обработка линейных списков 22 Рекурсия и итерация Функции fact(n) fct(n,1); fct(n,m) if n = 0 then m else fct( n 1, m n ); соответствует итеративный алгоритм m := 1; {n = n0 0} While n 0 do {инв: n0! = n! * m} m := n * m; n := n 1 od {m = n0!}

Рекурсивная обработка линейных списков 23 Схема программы и её интерпретация mm = 1; nn = 0; h(x, y) = x * y; g(x) = x – 1; f(x) = x! q(x, y) = x * y; m := mm; {n = n0} While n nn do {инв: f(n0) = q(f(n), m)} m := h (n, m); n := g(n) od {m = f(n0)}

Рекурсивная обработка линейных списков 24 Интерпретация со списками m и n mm = Nil; nn = Nil; h(x, y) = ConsHead (x, y) = Cons (Head (x), y); g(x) = Tail (x); f(x) = Reverse (x); q(x, y) = Concat (x, y); m := Nil; {n = n0} While n Nil do {инв: Reverse (n0) = Concat (Reverse (n), m) } m := ConsHead (n, m); n := Tail (n) od {m = Reverse (n0)}

Рекурсивная обработка линейных списков 25 m := Nil; {n = n0} While n Nil do {инв: Reverse (n0) = Concat(Reverse (n), m)} m := ConsHead (n, m); n := Tail (n) od {m = Reverse (n0)} n m n m Head(n)Tail(n)

Рекурсивная обработка линейных списков 26 Пример 1.7. Функция Reverse2, обращающая список. Введем вспомогательную функцию Rev, второй параметр которой используется как «накапливающий»: Rev(y, z) = if Null(y) then z else Rev (Tail(y), Cons (Head(y), z)); Тогда Reverse2 (y) = Rev (y, Nil). y z Tail(y)

Рекурсивная обработка линейных списков 27 Пример. Reverse2 (y) при y = (a b) ВызовыВозвращаемые значения Reverse2 ((a b)) Rev ((a b), Nil) Rev ((b), Cons(a, Nil)) * Cons (a, Nil) Rev (Nil, Cons (b, (a))) * Cons (b, (a))) (b a) (a) (b a)

Рекурсивная обработка линейных списков 28 Количество вызовов конструктора Cons при обращении функцией Reverse2 списка длины n. Q(n) = Q(n 1) + 1, Q(0) = 0 Q(n) = n (!) Ср. с R(n) = n(n + 1)/2

Рекурсивная обработка линейных списков 29 Формальное определение линейного списка См. с в файле «1Списки»

Рекурсивная обработка линейных списков 30 Определение скобочной записи линейного списка ::= | ::= Nil ::= ::= (. ) ::= Здесь L_list(El) – линейный список из элементов типа El, Null_list – пустой список, Non_null_list(El) – непустой линейный список, Head_l(El) – «голова» списка, Tail_l(El) – «хвост» списка, Pair(El) – упорядоченная пара «голова»–«хвост», т. е. элемент декартова произведения. Терминальные символы: Nil обозначает пустой список, (. ) использованы для обозначения элемента декартова произведения.

Рекурсивная обработка линейных списков 31 Примеры (a. (b. (c. (d. Nil)))) (a. (b. (c. (d )))) (a. (b. (c. (d )))) (a. (b. (c d ))) (a. (b c d )) (a b c d )) Полный вид Сокращенная запись Вариант (a. (b. (c. (d. Nil))))(a b c d)(a b c d)* (d. Nil)(d)(d)* Nil ( )

Рекурсивная обработка линейных списков 32 Функциональная спецификация линейного списка Базовые функции: индикатор Null (предикат: список пуст), селекторы Head («голова» списка) и Tail («хвост» списка), конструктор Cons 0) Nil: Null_list; 1) Null: L_list(El) Boolean; 2) Head: Non_null_list(El) El; 3) Tail: Non_null_list(El) L_list(El); 4) Cons: El L_list(El) Non_null_list(El); f(x) или f() обозначено f: A B f(x, y) или f(,) обозначено f: A B C

Рекурсивная обработка линейных списков 33 Система правил (аксиом) А1 А5 A1) Null(Nil) = true; A2) Null(Cons(x, y)) = false; A3) Head(Cons(x, y)) = x; A4) Tail(Cons(x, y)) = y; A5) Cons(Head(z), Tail(z)) = z. для всех x типа El, для всех y типа L_list( El ), для всех z типа Non_null_list( El )

Рекурсивная обработка линейных списков 34 Использование функции Cons для конструирования списков (a) = (a. Nil) = Cons(a, Nil); (a b c) = (a. (b. (c. Nil))) = Cons(a, Cons (b, Cons (c, Nil))). Построение каждой «точечной» пары (значения типа Pair( El ) ) требует однократного применения конструктора Cons. Определение типа Pair(El), не связанное с конкретным (скобочным) представлением : ::= Cons(, ) Это «операционное» представление списка Правило А5 становится при этом излишним и может быть выведено из аксиом А3, А4 (проверить!).

Рекурсивная обработка линейных списков 35 КОНЕЦ ЛЕКЦИИ