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

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

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

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

4 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 6 Иллюстрация Cons( Head(z), Tail(z)) = z Head(z) z Tail(z) Cons( Head(z), Tail(z) ) = z

7 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 13 Разборка и сборка при выполнении функции Concat(y, z) … y z

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

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

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

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

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

31 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 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 Рекурсивная обработка линейных списков 35 КОНЕЦ ЛЕКЦИИ