Иллюстрированный самоучитель по Mathematica 3/4

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

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

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

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

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

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

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

Обратите внимание на то, что функции Nest и FixedPoint дают единственный конечный результат, тогда как функции NestList и FixedPointList возвращают еще и все промежуточные результаты итераций. Последний пример иллюстрирует остановку вычислений по заданной погрешности, равной 10^-4.

Далее зададим функцию, реализующую алгоритм Ньютона для нахождения корня произвольного выражения f(x) при начальном значении х ₀ = а, по следующим формулам:

Эту функцию можно записать следующим образом:

Тогда вычисления корня из выражения е^x -2 с начальным приближением х ₀ = 0.5 при числе итераций n можно организовать с помощью функций Nest и NestList:

В первом случае возвращается только окончательный результат, а в других – еще и все промежуточные. Функция FixedPoint позволяет осуществлять итерации до тех пор, пока результат не перестанет изменяться (с машинной точностью). Это иллюстрирует следующий пример:

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