На этом шаге мы рассмотрим этот вид рекурсии.
К сложным типам рекурсии относятся:
- параллельная рекурсия;
- взаимная рекурсия;
- рекурсия высших порядков.
Параллельная рекурсия
- Определение.
- Параллельной рекурсией (рекурсией CAR-CDR, рекурсией по дереву) называется рекурсия, встречающаяся одновременно в нескольких аргументах функции.
Замечание. Название параллельной рекурсии "рекурсией по дереву" связано с тем, что её часто приходится использовать для обхода древовидных структур данных, т.е. списка, элементами которого являются списки.
Приведем примеры такой рекурсии.
-- Демонстрация использования параллельной рекурсии на -- примере функции, вычисляющей n-ое число Фибоначчи с -- помощью рекуррентного соотношения: -- -- f(0)=1, f(1)=1, f(x)=f(x-1)+f(x-2), x=2,3,... ------------------------------------------------- fibb:: Integer -> Integer fibb 0 = 1 fibb 1 = 1 fibb (n+1) = fibb n + fibb (n-1) -------------------------------- fibb':: Integer -> Integer fibb' n | n==0 = 1 | n==1 = 1 | True = fibb' (n-1) + fibb' (n-2) ------------------------------------------ fibb'':: Integer -> Integer fibb'' n | n==0 = 1 | n==1 = 1 | True = if even n then fibb'' t * fibb'' (t-1) + 2 * fibb'' (t-1) * fibb'' (t-1) + (-1)^t else 2 * fibb'' s * fibb'' (s+1) - fibb'' s * fibb'' s where t = n `div` 2 s = (n-1) `div` 2 -- *************************** -- Неудачные тестовые примеры: ---------------------------------------- test1 = fibb 11==144 && fibb 23==46368 test2 = fibb' 11==144 && fibb' 23==46368 test3 = fibb 30==fibb' 30 test4 = fibb'' 11==144 && fibb'' 23==46368 test5 = fibb'' 11==144 && fibb'' 23==46368 test6 = fibb'' 130 + fibb'' 131==fibb'' 132
-- Демонстрация использования параллельной рекурсии -- ************************************************ -- Функция, возвращающая число сочетаний из n эле- -- ментов по m с помощью рекуррентного соотношения -- -- m m m-1 0 -- C =C +C , C =1 -- n n-1 n-1 n -- -------------------------------- c:: Integer -> Integer-> Integer c n m | n<m || n<0 || m<0 = error "n>m & n,m>0" | n==m || m==0 = 1 | True = c (n-1) m + c (n-1) (m-1) ----------------------------------------------------- choose n 0 = 1 choose n k | n<k = 0 | n==k = 1 | True = choose (n-1) (k-1) + choose (n-1) k -- ************************************************* -- Функция (эффективная), возвращающая число сочета- -- ний из n элементов по m с помощью рекуррентного -- соотношения -- -- m n m-1 0 -- C = - * C , C =1 -- n m n-1 n ---------------------- binom n 0 = 1 binom n m | n<m = 0 | True = (n * binom (n-1) (m-1)) `div` m -- *********************************************** -- Неудачные тестовые примеры: ------------------------------ test1 = c 64 2 == 2016 && c 5 3 == 10 && c 13 5 == 1287 && c 4 3 == 4 && c 4 2 == 6 && c 99 98 == 99 ------------------------------ test2 = choose 64 2 == 2016 && choose 5 3 == 10 && choose 13 5 == 1287 && choose 4 3 == 4 && choose 4 2 == 6 && choose 99 98 == 99 ------------------------------ test3 = binom 64 2 == 2016 && binom 5 3 == 10 && binom 13 5 == 1287 && binom 4 3 == 4 && binom 4 2 == 6 && binom 99 98 == 99 ----------------------------- test4 n m = binom n m --------------------------------------------- -- Тестирование выполнения закона Ньютона для -- биномиальных коэффициентов -------------------------------------- test5 n m k = binom n m * binom m k == binom n k * binom (n-k) (m-k)
-- Демонстрация параллельной рекурсии на примере -- вычисления значения функции вида: -- -- f(0)=13, f(1)=17, f(2)=20, f(3)=30, -- -- f(2n)=43*f(n)+57*f(n+1), -- -- f(2n+1)=91*f(n)+179*f(n+1), n>=2 ------------------------------------ fD:: Integer -> Integer fD n | n==0 = 13 | n==1 = 17 | n==2 = 20 | n==3 = 30 | even n = 43*fD (n `div` 2) + 57*fD ((n `div` 2)+1) | True = 91*fD((n-1) `div` 2)+179*fD(((n-1) `div` 2)+1) -------------------------------------------------------------- res:: Int -> [Integer] res k = take k (map (fD) [0..]) -- **************************** -- Неудачные тестовые примеры: ------------------------------ test = res 100
На следующем шаге мы рассмотрим взаимную рекурсию.
