Реализация рекурсивных и рекуррентных алгоритмов
Рассмотрим несколько простых примеров, выявляющих суть функционального программирования. Вначале это будет пример, в котором задана функция sen [х, n], вычисляющая сумму синуса в степени n и косинуса в степени n:
scn[x_, n_] := Sin[x] ^ n + Cos[x] ^ n scn[1, 2] 1scn[x, 2] 1scn[x, n] Cos[x] n + Sin[x] nВ этом простейшем примере результат вычислений есть возвращаемое функцией sen значение – численное или символьное. В свою очередь, функция sen в своем теле имеет встроенные функции синуса и косинуса.
Важное место в решении многих математических задач занимают реализации рекурсивных и рекуррентных алгоритмов. Напомним, что рекурсия означает обращение функции к самой себе внутри ее тела, а рекуррентность – получение результата на данном шаге по результатам вычислений на предшествующих шагах.
Рассмотрим, как это делается, с помощью описанных выше функций. Классический пример реализации рекурсивного алгоритма – вычисление факториала путем задания функции, в теле которой есть обращение к ней же самой:
f[n_] := n * f[n - 1]; f[0] = 1; f[1] = 1;Полезно, однако, обратить внимание на возможность явного задания результата для конкретных значений аргумента: f [ 0 ] =1 и f [ 1 ] =1. Так что рекурсия реализуется, начиная с n=2 и выше, в соответствии с классическим определением факториала.
Для реализации рекуррентных алгоритмов в Mathematica имеется ряд функций, таких как Nest или FixedPoint. В следующих примерах показано вычисление квадратного корня из числа 5 по известному алгоритму Ньютона, записанному в виде функции newtonS:
newtonS [x_]: = N[ 1/2 (x + 5/x)] Nest[newton5, 1.0, 5] 2.23607 NestList [newtonS, 1.0, 5] {1., 3., 2.33333, 2.2381, 2.23607, 2.23607} FixedPoint [newtonS, 1.0] 2.23607 FixedPointList [newtonS, 1.0] {1., 3., 2.33333, 2.2381, 2.23607, 2.23607, 2.23607, 2.23607} FixedPointList [newtonS, 1.0, SameTest > (Abs[#1 -#2] < 10.A-4 &)] {1., 3., 2.33333, 2.2381, 2.23607, 2.23607}Обратите внимание на то, что функции Nest и FixedPoint дают единственный конечный результат, тогда как функции NestList и FixedPointList возвращают еще и все промежуточные результаты итераций. Последний пример иллюстрирует остановку вычислений по заданной погрешности, равной 10-4.
Далее зададим функцию, реализующую алгоритм Ньютона для нахождения корня произвольного выражения f(x) при начальном значении х 0 = а, по следующим формулам:
x0 = a; xn = xn - 1 - f(xn - 1) / f '(xn-1)Эту функцию можно записать следующим образом:
newtoniter[f_, x0_, n_] := Nest[(#-f[#] / f'[#]) &, N[x0], n]Тогда вычисления корня из выражения е^x -2 с начальным приближением х 0 = 0.5 при числе итераций n можно организовать с помощью функций Nest и NestList:
newtoniter [Function [ {x}, Exp[x] -2.0], 0.5, 5] 0.693147 newtoniter [Function [ {x}, Exp[x] -2.0], 0.5, #] & /@ Range [5] {0.713061, 0.693344, 0.693147, 0.693147, 0.693147} newtoniterl[f_,x0_,n_] := NestList[ (#-f [#] /f'[#]) &,N[x0], n] newtoniterl [Function [{x}, Exp[x] -2.0], 0.5, 5] {0.5, 0.713061, 0.693344, 0.693147, 0.693147, 0.693147}В первом случае возвращается только окончательный результат, а в других – еще и все промежуточные. Функция FixedPoint позволяет осуществлять итерации до тех пор, пока результат не перестанет изменяться (с машинной точностью). Это иллюстрирует следующий пример:
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
newtonfp[f_, x0_] := FixedPoint[(#-f[#] / f'[#]) &, N[xO]] newtonfp[Function[{x}, Exp[x] - 2.0], 0.5] 0.693147Более сложные примеры функционального программирования мы рассмотрим позже, при описании создания пакетов расширения систем Mathematica.