На этом шаге мы рассмотрим построение восходящей рекурсии.
Восходящая рекурсия
При рекурсивных вызовах функций используется большой объём памяти для хранения промежуточных результатов и адресов возврата значения рекурсивной функции.
Использование вспомогательных переменных, которые называются накапливающими параметрами, позволяет использовать память только для хранения адресов возврата значения функции.
В функциональном программировании возможно осуществить такой механизм с помощью восходящей рекурсии, используя вспомогательную функцию, с аргументами, которыми являются накапливающие параметры.
- Определение (описательное).
- Для реализации восходящей рекурсии к функции добавляется новый параметр, который называется накапливающим параметром (или параметром типа "рабочая память").
Промежуточные результаты вычисляются на каждой стадии рекурсии, при этом результат конструируется постепенно, хранится и передаётся в виде накапливающего параметра до тех пор, пока не будет достигнут терминальный случай. К этому времени результат уже содержится в накапливающем параметре и необходимо лишь вернуть его вызывающей функции верхнего уровня.
Приведём рецепт написания индуктивного определения функции в случае восходящей рекурсии [1, с.78-80; 2, с.152]:
- придумайте (!) функцию, имеющую один или несколько накапливающих параметров, один из которых будет содержать результат;
- для терминального случая положите значение функции равным значению некоторого накапливающего параметра;
- для нетерминального случая повторно вызовите функцию со значениями других ("главных") параметров, выраженными через "старые";
- вызовите функцию с начальными значениями накапливающих параметров;
- проведите тестирование и исправьте, если необходимо, начальные значения накапливающих параметров.
Приведем примеры построения рекурсии.
-- Демонстрация использования рекурсии по значению (или -- рекурсия с использованием накапливающего параметра) -- на примере функции, возвращающей факториал неотрица- -- тельного натурального числа ------------------------------ 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]
-- Демонстрация использования накапливающих параметров для -- реализации арифметических функций и предикатов в стиле -- вычислительной модели, называемой МНР (машиной с неог- -- раниченными регистрами) --------------------------------------------- -- Моделирование операции "вычитание единицы" -- При запуске res:=0, r3:=1 ------------------------------- sub1:: Int -> Int -> Int -> Int sub1 res x r3 | r3==x = res | True = sub1 (res+1) x (r3+1) ----------------------------------------------- -- Моделирование операции "сложение двух чисел" -- При запуске res:=x, r4:=0 ------------------------------------- add:: Int -> Int -> Int -> Int -> Int add res x y r4 | y==r4 = res | True = add (res+1) x y (r4+1) ------------------------------------------------ -- Моделирование операции "умножение двух чисел" -- При запуске res:=0 ------------------------------ mul:: Int -> Int -> Int -> Int mul res x y | y==0 = res | True = mul (res+x) x (y-1) ------------------------------------------------ -- Моделирование операции "вычитание двух чисел" -- При запуске res:=x ------------------------------ sub:: Int -> Int -> Int -> Int sub res x y | y==0 = res | True = sub (res-1) x (y-1) ------------------------------------------------ -- Моделирование операции "целочисленное деление -- двух чисел". -- При запуске res:=0, r4:=x -------------------------------------- div':: Int -> Int -> Int -> Int -> Int div' res x y r4 | r4<y = res | True = div' (res+1) x y (r4-y) -------------------------------------------------- -- Моделирование предиката "сравнение двух чисел": -- -- |0, x>=y; -- f(x,y)=| -- |1, x<y -- -- При запуске res:=0, r4:=0 -------------------------------------- less:: Int -> Int -> Int -> Int -> Int less res x y r4 | x==y = res | y==r4 = res | x==r4 = 1 | True = less res x y (r4+1) ------------------------------------------------- -- Моделирование операции "нахождение наибольшего -- общего делителя (НОД)". -- При запуске res:=0 ------------------------------ nod:: Int -> Int -> Int -> Int nod res x y | x==0 = y | y==0 = x | x>=y = nod res (x-y) y | True = nod res x (y-x) ------------------------------------ -- Неудачные тестовые примеры: ------------------------------ test1 = sub1 0 11 1 == 10 ---------------------------- test2 = add 5 5 10 0 == 15 && add 2 2 3 0 == 5 ----------------------------- test3 = mul 0 5 10 == 50 && mul 0 7 111 == 777 && mul 0 12 10 == 120 ----------------------------- test4 = sub 11 11 6 == 5 ----------------------------- test5 = div' 0 10 5 10 == 2 && div' 0 21 5 21 == 4 && div' 0 32 8 32 == 4 ----------------------------- test6 = less 0 5 4 0 == 0 && less 0 4 5 0 == 1 && less 0 5 5 0 == 0 --------------------------- test7 = nod 0 5 3 == 1 && nod 0 2 6 == 2 && nod 0 18 24 == 6 -------------------------- {- Программа вычисления произведения двух чисел. R2:=x, R3:=y, R1 - содержит результат операции ПРОГРАММА I1 J(3,4,20) I2 T(1,5) Регистры R5, R6, R7 используются для вычисления I3 T(2,6) res+x (см. функцию на языке Haskell) I4 J(6,7,8) I5 S(5) I6 S(7) I7 J(1,1,4) I8 T(5,1) I9 Z(7) I10 T(3,8) Регистры R8, R9, R10 используются для вычисления I11 J(8,10,16) y-1 (см. функцию на языке Haskell) I12 S(9) I13 J(8,9,16) I14 S(10) I15 J(1,1,12) I16 T(10,3) I17 Z(9) I18 Z(10) I19 J(1,1,1) -}
(1)Грей П. Логика, алгебра и базы данных.- М., Машиностроение,1989,- 368 с.
(2)Душкин Р.В. Функциональное программирование на языке Haskell. - М.: ДМК Пресс, 2007. - 608 с.
На следующем шаге мы рассмотрим сложные типы рекурсии на числовых структурах.
