На этом шаге мы рассмотрим рекурсию такого вида и приведем примеры ее использования.
- Определение.
- Будем говорить, что в функции F присутствует рекурсия по аргументам, если в качестве результата функция возвращает значение другой функции G, при этом в вычислении аргументов этой функции участвует рекурсивный вызов F.
Приведем примеры такой рекурсии.
-- Демонстрация использования рекурсии по аргументам на -- примере вычисления факториала неотрицательного числа -- (рекурсивный вызов является аргументом умножения) -- ************************************************* -- Реализация с помощью охранных выражений ------------------------------------------ fact1:: Integer -> Integer fact1 n | n==0 = 1 | True = n * fact1 (n-1) ------------------------------------------------ -- Реализация с помощью сопоставления с образцом ------------------------------------------------ fact2:: Integer -> Integer fact2 0 = 1 fact2 (n+1) = (n+1) * fact2 n ------------------------------------------ -- Реализация с использованием альтернатив ------------------------------------------ fact3:: Integer -> Integer fact3 n = if n==0 then 1 else n * fact3 (n-1) -- ***************************** -- Неудачные тестовые примеры: ------------------------------ test = fact1 0==1 && fact1 10==3628800 && fact1 40==815915283247897734345611269596115894272000000000 && fact2 5==120 && fact2 40==815915283247897734345611269596115894272000000000 && fact3 40==815915283247897734345611269596115894272000000000
-- Демонстрация рекурсивного компьютерного решения клас- -- сических задач индийского математика С.Рамануджана, -- который решил их без использования компьютера. -- Демонстрация опасностей "вещественной" арифметики -- ************************************************* -- Функция возвращает значение выражения -- -- Sqrt(a+Sqrt(a+Sqrt(a+...))), -- -- n - количество используемых квадратных корней ------------------------------------------------ raman1 n a | n==1 = sqrt a | True = sqrt (a+raman1 (n-1) a) ------------------------------------------- -- Функция возвращает значение выражения -- -- Sqrt(1+a*(Sqrt(1+(a+1)*(Sqrt(1+(a+2)*(Sqrt(1+...))))))), -- -- где: a - натуральное число, -- n - количество используемых квадратных корней ----------------------------------------------------- raman2 n a | n==1 = sqrt (1.0+a) | True = sqrt (1.0+a*raman2 (n-1) (a+1.0)) -- ************************************************** -- Неудачные тестовые примеры: ------------------------------------------------- test1 = abs ((raman1 100 2)-2) < 0.00000000001 && abs ((raman1 50 2)-2) < 0.00000000001 && abs ((raman1 100 6)-3) < 0.00000000001 && abs ((raman1 100 12)-4) < 0.00000000001 && abs ((raman1 100 5)-(1+sqrt 21)/2) < 0.000001 -------------------------------------------- test2 = abs ((raman2 30 2)-3) < 0.00000001 && abs ((raman2 20 2)-3) < 0.00001 ----------------------------------------- -- Удачный тестовый пример: ---------------------------------------- test21 = abs ((raman2 10 2)-3) < 0.00001 ------------------------------------------------- -- В этом и подобных случаях вначале ищите ошибку -- в тесте, а лишь затем - в самой программе. -- Исправляем тест, и он становится неудачным: ---------------------------------------------- test22 = abs ((raman2 20 2)-3) < 0.00001 && abs ((raman2 10 2)-3) < 0.01 ----------------------------------------------- test = test1 && test2 && not (test21) && test22
-- Демонстрация использования рекурсии -- по аргументам для решения: -- (1) трёх задач С.Рамануджана; -- (2) задачи Ф.Виета -------------------------------------------- -- Функция f62 возвращает значение выражения -- -- Sqrt(6+2*Sqrt(7+3*Sqrt(8+4*Sqrt(9+...))), -- ------------------------------------------ f62:: Double -> Double -> Double -> Double f62 n a b | n==1 = sqrt 6.0 | True = sqrt (a+b*f62 (n-1) (a+1) (b+1)) --------------------------------------------------- f8:: Integer -> Double f8 n | n==1 = sqrt (8.0-sqrt(8.0+sqrt 8.0)) | True = sqrt (8.0-sqrt(8.0+sqrt (8.0-f8 (n-1)))) ------------------------------------------------------ f23:: Integer -> Double f23 n | n==1 = sqrt (23.0-2*sqrt(23.0+2*sqrt 23.0)) | True = sqrt (23.0-2*sqrt(23.0+ 2*sqrt(23.0+2*f23 (n-1)))) ----------------------------------------------------------- -- Внимание! При решении использован функционал map... ------------------------------------------------------ piVieta:: Double piVieta = product (map coeff [1..10]) where coeff n | n==1 = sqrt (1/2) | True = sqrt (1/2+1/2*coeff (n-1)) ------------------------------------------------------ -- Неудачные тестовые примеры: ------------------------------ test1:: (Double,Integer) test1 = (f62 100 6 2,4) ----------------------------- test2,test3:: (Double,Double) test2 = (f8 200,otvet) where otvet = 1.0+2.0*sqrt (3.0)*sin (pi/9.0) test3 = (f23 300, otvet) where otvet = 1.0+4.0*sqrt (3.0)*sin (pi/9.0) -------------------------------------------------------- test4 = (piVieta,2/pi)
На следующем шаге мы рассмотрим рекурсию по значению.
