# Глава 16. Рекурсия Чтобы понять рекурсию, нужно сначала понять рекурсию. Эта старая шутка про рекурсию иногда пугает новичков, как в своё время напугала и меня. В действительности в рекурсии нет ничего страшного, и в этой главе мы познакомимся с этим важным механизмом. ## Цикл Удивительно, но в Haskell нет встроенных циклических конструкций, столь привычных для других языков. Ни тебе `for`, ни тебе `while`. Однако обойтись без циклов в нашем коде мы не сможем. Как же нам их организовывать? К счастью, чаще всего нам это и не нужно. [Вспомним](/courses/haskell/chapters/haskell_chapter_0140#block-map) нашу знакомую, функцию `map`: ```haskell map toUpper someList ``` Ну и чем же не цикл? На том же C это выглядело бы как-то так: ```c++ int length = ... for(int i = 0; i < length; ++i) { char result = toUpper(someList[i]); ... } ``` Функции наподобие `map` в подавляющем большинстве случаев избавляют нас от написания явных циклических конструкций, и это не может не радовать. Однако изредка нам всё-так придётся писать циклы явно. В Haskell, из-за отсутствия `for`-конструкции, сделать это можно только одним способом — через рекурсию (англ. recursion). **Идея рекурсии** предельно проста: если нам нужно повторить вычисление, производимое некой функцией, мы должны применить эту функцию внутри себя самой. И получится зацикливание. Для расчета факториала числа в Haskell можно воспользоваться встроенной функцией `product`: `fact n = product [1..n]`. Мы [рассматривали](/courses/haskell/chapters/haskell_chapter_0090/#block-useful-functions) ее в главе про списки. {.task_text} Однако с целью тренировки почему бы не написать и рекурсивный вариант? Реализуйте функцию `fact` с использованием рекурсии. {.task_text} Помните, что в рекурсивной функции должно быть как правило зацикливания, так и правило выхода из цикла. {.task_text} ```haskell {.task_source #haskell_chapter_0160_task_0010} module Main where -- Your code here main :: IO () main = do print $ fact 0 print $ fact 1 print $ fact 2 print $ fact 3 print $ fact 4 print $ fact 5 ``` Факториал нуля равен 1. Факториал числа `n` равен `n`, умноженному на факториал от `n - 1`. {.task_hint} ```haskell {.task_answer} module Main where fact :: Int -> Int fact n = if n == 0 then 1 else n * fact(n-1) main :: IO () main = do print $ fact 0 print $ fact 1 print $ fact 2 print $ fact 3 print $ fact 4 print $ fact 5 ``` Напишите функцию `myGcd a b`, которая находит наибольший общий делитель (GCD, greatest common divisor) чисел `a` и `b`. Функция должна быть рекурсивной. Название функции начинается с `my`, потому что в Haskell есть стандартная функция `gcd`, которая делает то же самое. {.task_text} Например, `myGcd 25 15` вернет 5, а `myGcd 8 3` вернет 1. {.task_text} В своем решении используйте алгоритм Евклида. Он заключается в следующем: {.task_text} - GCD равен `a`, если `a` и `b` совпадают. - GCD равен GCD от `a - b` и `b`, если `a` больше `b`. - GCD равен GCD от `a` и `b - a`, если `a` меньше `b`. ```haskell {.task_source #haskell_chapter_0160_task_0020} module Main where -- Your code here main :: IO() main = do print $ myGcd 25 15 print $ myGcd 8 3 print $ myGcd 14 49 ``` Вы можете воспользоваться цепочкой определений `function arg | COND1 = EXPR1 | ...`. {.task_hint} ```haskell {.task_answer} module Main where myGcd :: Int -> Int -> Int myGcd a b | a == b = a | a > b = myGcd (a-b) b | otherwise = myGcd a (b-a) main :: IO() main = do print $ myGcd 25 15 print $ myGcd 8 3 print $ myGcd 14 49 ``` Взглянем на определение функции `map`: ```haskell map _ [] = [] map f (x:xs) = f x : map f xs ``` А теперь разберём это интереснейшее определение по косточкам. ## Правда о списке Первым аргументом, как мы помним, выступает некая функция, а вторым — список, к элементам которого применяется эта функция. Но что это за странного вида конструкция в круглых скобках? ```haskell (x:xs) ``` Это — особый образец, используемый для работы со списками. И чтобы он стал понятен, я должен рассказать вам правду о формировании списка. Как мы помним, формируется список предельно просто: {#block-list} ```haskell [1, 2, 3] -- Список из трёх целых чисел. ``` Однако в действительности он формируется несколько иначе. Привычная нам конструкция в квадратных скобках есть ни что иное, как синтаксический сахар (англ. syntactic sugar). Синтаксическим сахаром называют некое упрощение кода, делающее его слаще, приятнее для нас. Если же мы уберём сахар (или, как ещё говорят, рассахарим код), то увидим вот что: ```haskell 1 : 2 : 3 : [] ``` Именно так список из трёх целых чисел формируется на самом деле. Стандартный оператор `:` нам уже знаком, мы [встретились](/courses/haskell/chapters/haskell_chapter_0090#block-immutability) с ним в главе о списках: ```haskell newHost : hosts ``` Оператор `:` известен как оператор cons (от слова construct) и сооружает список, добавляя левый операнд в начало списка — правого операнда. То есть список строится путём добавления элемента в его «голову», начиная с пустого списка: ```haskell 1 : 2 : 3 : [] = 1 : 2 : [3] = 1 : [2, 3] = [1, 2, 3] ``` Начиная с правого края, мы сначала применяем оператор `:` к `3` и пустому списку, в результате чего получаем список с единственным элементом `[3]`. Затем, применяя второй оператор `:` к `2` и к только что полученному списку `[3]`, мы получаем новый список `[2, 3]`. И в конце, вновь применив оператор `:` к `1` и к списку `[2, 3]`, мы получаем итоговый список `[1, 2, 3]`. Вот почему столь удобно оперировать «головой» и «хвостом» списка. И именно поэтому был создан особый образец для паттерн-матчинговой работы со списком: ```haskell (head : tail) ``` В данном случае слова `head` и `tail` не относятся к стандартным функциям, я лишь показываю назначение элементов данного образца. Вот более живой пример: ```haskell {.example_for_playground} main :: IO () main = print first where (first:others) = ["He", "Li", "Be"] ``` Поскольку мы точно знаем, что справа у нас список, слева мы пишем образец для списка, в котором `first` ассоциирован с первым элементом, с «головой», а шаблон `others` — с оставшимися элементами, с «хвостом». Но вы спросите, зачем нам это нужно? Если уж мы так хотим работать со списком через паттерн матчинг, можно ведь воспользоваться явным образцом: ```haskell {.example_for_playground} main :: IO () main = print first where [first, second, third] = ["He", "Li", "Be"] ``` Всё верно, однако образец с круглыми скобками чрезвычайно удобен именно для рекурсивной работы со списком, и вот почему. Вспомним определение функции `map`: ```haskell map f (x:xs) = f x : map f xs ``` Подставим реальные значения на основе примера про перевод символов строки в верхний регистр: ```haskell map f (x:xs) = f x : map f xs map toUpper "neon" = toUpper 'n' : map toUpper "eon" ``` Вот теперь-то мы видим, каким образом функция `map` пробегается по всему списку. Пройдёмся по итерациям, чтобы всё окончательно встало на свои места. У нас же цикл, верно? А где цикл — там итерации. На первой из них оператор `:` применяется к выражениям `toUpper 'n'` и `map toUpper "eon"`. Выражение слева вычисляется и даёт нам символ `'N'`: ```haskell toUpper 'n' : map toUpper "eon" 'N' : map toUpper "eon" ``` Выражение справа содержит применение той же функции `map`, то есть мы входим в цикл, во вторую его итерацию: ```haskell map toUpper "eon" = toUpper 'e' : map toUpper "on" ``` Выражение слева вычисляется и даёт нам `'E'`: ```haskell toUpper 'e' : map toUpper "on" 'E' : map toUpper "on" ``` Вычисляем выражение справа — и входим в следующую итерацию: ```haskell map toUpper "on" = toUpper 'o' : map toUpper "n" ``` Выражение слева даёт нам `'O'`: ```haskell toUpper 'o' : map toUpper "n" 'O' : map toUpper "n" ``` Справа вновь применение `map` — и наша последняя итерация: ```haskell map toUpper "n" = toUpper 'n' : map toUpper [] ``` Выражение слева даёт нам `'N'`: ```haskell toUpper 'n' : map toUpper [] 'N' : map toUpper [] ``` Мы вытащили из списка последний из четырёх символов, и список остался пустым. Что же мы будем делать дальше? А дальше мы вспоминаем первый вариант определения функции `map`: ```haskell map _ [] = [] ``` Здесь функция говорит: «Как только я вторым аргументом получу пустой список, я, игнорируя первый аргумент, немедленно дам тот же самый пустой список». Поэтому оставшееся на последней итерации выражение справа: ```haskell map toUpper [] ``` подойдёт под данный случай и просто даст нам пустой список. Всё, готово, работа функции завершена. На каждой итерации мы откусываем «голову» списка и передаём её функции `toUpper`, «хвост» же передаём вновь функции `map`. На четвёртой итерации упираемся в пустой список и возвращаем его же. Совместив все итерации воедино, получаем вот что: ```haskell 'N' : 'E' : 'O' : 'N' : [] ``` Узнаёте? Это же наш рассахаренный список, соединяющийся воедино: ```haskell ['N', 'E', 'O', 'N'] ``` Вот мы и пришли к нашему равенству: ```haskell map toUpper "neon" = map toUpper ['n', 'e', 'o', 'n'] = ['N', 'E', 'O', 'N'] = "NEON" ``` Напишите собственную функцию `myLength`, которая принимает список и возвращает его длину. {.task_text} ```haskell {.task_source #haskell_chapter_0160_task_0030} module Main where -- Your code here main :: IO() main = do print $ myLength [] print $ myLength [1] print $ myLength [1, 2, 3] print $ myLength [1, 2, 3, 4, 5, 6] ``` Длина пустого списка равна нулю. Длина не пустого списка равна сумме 1 и длины хвоста списка. {.task_hint} ```haskell {.task_answer} module Main where myLength :: [Int] -> Int myLength [] = 0 myLength (_:t) = 1 + myLength t main :: IO() main = do print $ myLength [] print $ myLength [1] print $ myLength [1, 2, 3] print $ myLength [1, 2, 3, 4, 5, 6] ``` ## Туда и обратно Определяя рекурсивную функцию, важно помнить о том, что в ней должно быть как правило зацикливания, так и правило выхода из цикла: ```haskell map _ [] = [] -- Выходим из цикла. map f (x:xs) = f x : map f xs -- Зацикливаемся, -- применяя саму себя. ``` Если бы мы опустили первое определение, компилятор предусмотрительно сообщил бы нам о проблеме: ```bash Pattern match(es) are non-exhaustive ``` И это совершенно правильно: если на каждой итерации мы уменьшаем список, то рано или поздно список точно останется пустым, а следовательно, мы обязаны объяснить, что же делать в этом случае. Напишите собственную функцию `myReverse`, которая принимает список и переворачивает его. {.task_text} ```haskell {.task_source #haskell_chapter_0160_task_0040} module Main where -- Your code here main :: IO() main = do print $ myReverse [] print $ myReverse [1] print $ myReverse [1, 2, 3] print $ myReverse [1, 2, 3, 4, 5, 6] ``` В своем решении вы можете использовать оператор для конкатенации списков `++`. {.task_hint} ```haskell {.task_answer} module Main where myReverse :: [Int] -> [Int] myReverse [] = [] myReverse (h:t) = (myReverse t) ++ [h] main :: IO() main = do print $ myReverse [] print $ myReverse [1] print $ myReverse [1, 2, 3] print $ myReverse [1, 2, 3, 4, 5, 6] ``` Напишите собственную функцию `myTake n lst`, которая возвращает список, состоящий из первых `n` элементов списка `lst`. {.task_text} ```haskell {.task_source #haskell_chapter_0160_task_0050} module Main where -- Your code here main :: IO() main = do print $ myTake 5 [] print $ myTake 0 [1, 2] print $ myTake 1 [1, 2, 3] print $ myTake 3 [1, 2, 3, 4, 5, 6] print $ myTake 6 [1, 2, 3, 4, 5, 6] print $ myTake 100 [1, 2, 3, 4, 5, 6] ``` В своем решении вы можете использовать оператор для конкатенации списков `++`. {.task_hint} ```haskell {.task_answer} module Main where myTake :: Int -> [Int] -> [Int] myTake _ [] = [] myTake 0 _ = [] myTake n (h:t) = [h] ++ myTake (n-1) t main :: IO() main = do print $ myTake 5 [] print $ myTake 0 [1, 2] print $ myTake 1 [1, 2, 3] print $ myTake 3 [1, 2, 3, 4, 5, 6] print $ myTake 6 [1, 2, 3, 4, 5, 6] print $ myTake 100 [1, 2, 3, 4, 5, 6] ``` В некоторых случаях для реализации рекурсивных функций удобно использовать вспомогательные выражения внутри блока `let` или `where`. Например, требуется определить индекс искомого элемента в списке. Для этого функция принимает два аргумента: искомое значение и список. Но для реализации рекурсивного поиска нам бы пригодился аргумент-счетчик, инициализируемый нулем и увеличиваемый на каждом шаге рекурсии. Он и означал бы индекс элемента в списке. Чтобы не выносить его в объявление функции, можно завести внутреннюю функцию. Потренируйтесь. {#block-task-indexof} Напишите функцию `indexOf`, которая принимает два аргумента: целочисленное значение и список. Функция должна вернуть индекс первого вхождения заданного значения в список. Либо -1, если оно не найдено. {.task_text} ```haskell {.task_source #haskell_chapter_0160_task_0060} module Main where -- Your code here main :: IO () main = do print $ indexOf 5 [] print $ indexOf 5 [1, 2, 3] print $ indexOf 5 [5] print $ indexOf 5 [5, 10] print $ indexOf 5 [1, 5] print $ indexOf 5 [1, 5, 5] print $ indexOf 5 [1, 2, 3, 4, 5, 6] ``` Заведите внутреннюю функцию `findVal`, которая принимает текущий индекс и список. Если список пустой, она возвращает -1. Если список не пустой, то его голова сравнивается с искомым значением. При совпадении функция возвращает индекс. Иначе возвращает собственное рекурсивное применение к увеличенному на 1 значению индекса и хвосту списка. Все, что останется сделать в теле функции `indexOf` — это вызвать `findVal` от индекса 0 и списка. {.task_hint} ```haskell {.task_answer} module Main where indexOf :: Int -> [Int] -> Int indexOf val lst = findVal 0 lst where findVal :: Int -> [Int] -> Int findVal _ [] = -1 findVal index (h:t) | val == h = index | otherwise = findVal (index + 1) t main :: IO () main = do print $ indexOf 5 [] print $ indexOf 5 [1, 2, 3] print $ indexOf 5 [5] print $ indexOf 5 [5, 10] print $ indexOf 5 [1, 5] print $ indexOf 5 [1, 5, 5] print $ indexOf 5 [1, 2, 3, 4, 5, 6] ``` ## Для любопытных Открою секрет: рекурсивными в Haskell бывают не только функции, но и типы. Но об этом в последующих главах.