Реализация рекурсивных и рекуррентных алгоритмов

Рассмотрим несколько простых примеров, выявляющих суть функционального программирования. Вначале это будет пример, в котором задана функция sen [х, n], вычисляющая сумму синуса в степени n и косинуса в степени n:

scn[x_, n_] := Sin[x]^n + Cos[х]^n

scn[l, 2]

scn[x, 2]

scn[x, n]

Cos[x]n+ Sin[x]n

В этом простейшем примере результат вычислений есть возвращаемое функцией sen значение — численное или символьное. В свою очередь, функция sen в своем теле имеет встроенные функции синуса и косинуса.

Важное место в решении многих математических задач занимают реализации рекурсивных и рекуррентных алгоритмов. Напомним, что рекурсия означает обращение функции к самой себе внутри ее тела, а рекуррентность — получение результата на данном шаге по результатам вычислений на предшествующих шагах.

Рассмотрим, как это делается, с помощью описанных выше функций. Классический пример реализации рекурсивного алгоритма — вычисление факториала путем задания функции, в теле которой есть обращение к ней же самой:

f[n_] :=n*f[n-1];f[0]=l;f[1]=1;

Полезно, однако, обратить внимание на возможность явного задания результата для конкретных значений аргумента: f [ 0 ] =1 и f [ 1 ] =1. Так что рекурсия реализуется, начиная с n=2 и выше, в соответствии с классическим определением факториала.

Для реализации рекуррентных алгоритмов в Mathematica имеется ряд функций, таких как Nest или FixedPoint. В следующих примерах показано вычисление

квадратного корня из числа 5 по известному алгоритму Ньютона, записанному в виде функции newtonS:

newtonS [x_] := N[ 1/2 ( х + 5/х )]

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[#l- #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 [ {х} , Ехр[х] - 2.0], 0.5, 5]

0.693147

newtoniter [Function [ {х }, Ехр[х] - 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 позволяет осуществлять итерации

до тех пор, пока результат не перестанет изменяться (с машинной точностью). Это иллюстрирует следующий пример:

newtonfp[f_, х0_] := FixedPoint[ (# - f [#]/f'[#]) &, N[xO]]

newtonfp[Function[{x} , Exp[x] - 2.0], 0.5]

0.693147

Более сложные примеры функционального программирования мы рассмотрим позже, при описании создания пакетов расширения систем Mathematica.

Содержание раздела