Создание простейших рекурсивных программ. Функции работы со строками и множествами. Сообщения об ошибках и преобразования типов.
Создание простейших рекурсивных программ.
В функциональных (и логических) языках программирования основным вычислительным средством является рекурсия. Понятие рекурсии легко усвоится теми, кто хорошо знаком с математическим методом индукции. Давайте разберем подробно простую рекурсивную функцию, которая находит сумму элементов числового списка. В Haskell стандартная функция sum определена через функцию высшего порядка foldl, которую мы будем изучать позже, поэтому напишем здесь свою функцию следующим образом:
sum [] = 0
sum (x:xs) = x + sum xs
Почему у нас две строки с именем функции и что они означают? В первой строке записана база рекурсии – для пустого списка сумма элементов будет равна нулю. Базу рекурсии при работе со списками обычно пишут для пустого или одноэлементного списка. В нашем случае можно было бы записать базу и так:
sum [x] = x
то есть сумма элементов списка с одним единственным элементом равна этому элементу.
Разберем далее вторую строку. Выражение (x:xs) не следует принимать за ошибочно написанный кортеж, а трактовать так – «аргумент-список представимый в виде головы (первого элемента) x и хвоста (всех остальных элементов) xs». После знака равенства записана основная часть функции – шаг рекурсии. Разберем подробно как именно её следует составлять. Пусть у нас есть простой список [1,2,3], в качестве результата применения нашей функции к нему должно получиться значение 6. При первом обращении к функции с аргументом [1,2,3] у нас произойдет сравнение с образцом нашего списка [1,2,3] с аргументом в первой строке – с пустым списком. Сравнение успехом не увенчается, и компилятор перейдет ко второй строке, при этом у нас будет считаться x=1 и xs=[2,3] . Для написания рекурсивного выражения следует задать себе вопрос – пусть нам известен результат применения нашей функции к хвосту списка, как получить результат для самого списка? Результатом для хвоста списка [2,3] является число 5. Итак, у нас есть голова списка x=1, результат для хвоста 5 и мы хотим из этого получить результат 6, что следует сделать? Конечно же, сложить голову x=1 со значением 5, а это значение, как мы помним, результат применения нашей функции к хвосту списка, то есть вызов нашей функции с аргументом xs.
|
|
|
Давайте рассмотрим подробно как компилятор выполняет нашу рекурсивную функцию. В таблице 2.1 показан каждый шаг вызовов функции и состояние стека.
Таблица 2.1 Вычисление функции sum
| Функция | Вычисление тела функции | Результат | Стек | |
| 1 | sum [1,2,3] | 1+sum [2,3] | - | - |
| 2 | sum [2,3] | 2+sum [3] | - | sum [1,2,3] |
| 3 | sum [3] | 3+sum [] | - | sum [2,3] sum [1,2,3] |
| 4 | sum [] | 0 | 0 | sum [3] sum [2,3] sum [1,2,3] |
| 5 | sum [3] | 3+0 | 3 | sum [2,3] sum [1,2,3] |
| 6 | sum [2,3] | 2+3 | 5 | sum [1,2,3] |
| 7 | sum [1,2,3] | 1+5 | 6 | - |
|
|
|
Можно заметить, что наша функция не очень эффективна, после выполнения базы рекурсии пришлось выполнять шаги 5-7 по извлечению из стека предыдущих обращений к функции и вычислению результатов.
Давайте вспомним, как мы решали задачу нахождения суммы элементов массива в императивных языках программирования. Обычно заводилась переменная, в которую постепенно добавлялись очередные элементы, до тех пор, пока массив не заканчивался. Попробуем применить тот же подход. Для этого введем в нашу функцию дополнительный аргумент, в котором будет накапливаться вычисляемое значение – такой аргумент называют еще аккумулятором.
sum1 [] s = s
sum1 (x:xs) s = sum1 xs (s+x)
В этом варианте ответ будет уже получен на шаге 4, вычислений на шагах 5-7 в нашем примере не понадобится. Неудобство, заключающееся во введении нового аргумента, легко преодолеть, достаточно вызывать новую функцию из другой, имеющей один привычный аргумент и начальное значение аккумулятора.
sum a = sum1 a 0
sum1 [] s = s
sum1 (x:xs) s = sum1 xs (s+x)
Такая рекурсия еще называется хвостовой. В дальнейшем при изучении языка Пролог будет дано очень простое и наглядное определение хвостовой рекурсии. Пока же можно сказать так: при хвостовой рекурсии тело функции есть либо новая функция, в которой нет вызова нашей исходной функции, либо наша исходная функция, возможно с другими аргументами. Первый вариант не удовлетворял этому определению, так как в строке
|
|
|
sum (x:xs) = x + sum xs
происходит вычисление функции арифметического сложения с вызовом нашей исходной функции. А функция sum1 удовлетворяет определению – в ней происходит либо возврат аккумулятора - новая функция без вызова исходной, либо вызов исходной функции с другими аргументами. Использование хвостовой рекурсии с точки зрения программиста более эффективно, с другой стороны, рекурсия, соответствующая в точности математическому определению, кажется более привлекательной для математиков.
В примере выполнения лабораторной работы 2 ниже разобраны еще несколько задач с использованием рекурсии, но не хвостовой. Рекомендуется самостоятельно попробовать написать варианты хвостовой рекурсии.
Дата добавления: 2019-03-09; просмотров: 342; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!