На этом шаге мы рассмотрим рекурсию такого вида и приведем примеры ее использования.
- Определение.
- Будем говорить, что в функции F на языке Haskell присутствует рекурсия по значению, если в качестве результата возвращается значение функции F.
Частным случаем рекурсии по значению является хвостовая рекурсия.
- Определение ([1, с.151]).
- Хвостовой рекурсией называется специальный вид рекурсии, в которой имеется единственный вызов рекурсивной функции, и при этом этот вызов выполняется после всех вычислений.
В функциональном программировании часто для реализации хвостовой рекурсии увеличивают количество аргументов функции с помощью аргументов, в которых фиксируется состояние внешней среды.
Приведем примеры такой рекурсии.
-- Демонстрация использования рекурсии по значению (или -- рекурсия с использованием накапливающего параметра) -- на примере функции, возвращающей факториал неотрица- -- тельного натурального числа ------------------------------ fac:: Integer -> Integer fac n = fac1 n 1 where fac1 n m | n==1 = m | True = fac1 (n-1) n*m ----------------------------------------- -- Функция, возвращающая 1!+2!+3!+...+k! ---------------------------------------- summaF:: Integer -> Integer summaF k = sum (map fac [1..k]) ------------------------------- -- Неудачные тестовые примеры: ------------------------------------------- test1 = fac 5 == 120 && fac 100 `div` 100 `div` 99 == fac 98 && fac 82 `div` 82 == fac 81 && fac 1000 == product [1..1000] --------------------------------------------------------- test2 = summaF 6==sum [1,2,6,24,fac 5,fac 6]
Хвостовой рекурсии в императивном программировании соответствует цикл, а "хороший" транслятор функционального языка должен "уметь" распознавать хвостовую рекурсию и реализовывать её в виде цикла.
(1)Душкин Р.В. Функциональное программирование на языке Haskell. - М.: ДМК Пресс, 2007. - 608 с.
На следующем шаге мы рассмотрим рекурсию по значению и по аргументам.
