Рекурсия
Контрольные примеры.
fiboo(0)=1 fiboo(1)=1 fiboo(10)=89
fiboo(200) ® 453973694165307953197296969697410619233826
- Алгоритм Ламберта вычисления e
Задача 7. Составить программу вычисления приближения к основанию натуральных логарифмов, то есть к числу е, используя следующий алгоритм Ламберта:
![]()
![]()
![]()
Решение. Указанный алгоритм предложен Ламбертом в 1766 году [6, с.70]. Организовать по нему рекурсивные вычисления труда не составляет. Здесь величины a(k) и b(k) задаются рекуррентными соотношениями, похожими на определение чисел Фибоначчи, но нелинейными. Однако это обстоятельство не привносит каких-либо дополнительных затруднений в программную реализацию соответствующих функций. Дело в том, что задание последовательности любыми рекуррентными соотношениями сразу решает проблему триады: осуществлена параметризация задачи, выделена база и задана декомпозиция.
Программа e(k) приближенно вычисляет e, обращаясь к рекурсивным функциям-подпрограммам a(k) и b(k):
![]()
![]()

Учитывая, что последовательности a(k) и b(k) (k=0,1,2, …) определяются весьма схожим образом, можно построить одну общую функцию двух переменных для вычисления их членов. Отсюда ещё один вариант решения поставленной задачи:
![]()

Контрольный пример.
![]()
Мы видим, что уже е(5) » e с точностью до 9 знаков после десятичной точки, а начиная с e(8) уже все 15 знаков после точки верные. Если была бы необходимость вычислять по алгоритму Ламберта число e с большей точностью, то пришлось бы программно реализовывать арифметику длинных чисел.
Замечание. Предложенные варианты вычисления e можно было бы сделать существенно более эффективными, организовав в них динамические базы, пополняемые в процессе вычислений уже найденными значениями. Тем самым, исключив повторные вычисления элементов последовательностей, можно было бы вычислять a(k), b(k) и d(k,t) за k рекурсивных обращений.
- Наибольший общий делитель
Задача 8. Составить программу-функцию возвращающую наибольший общий делитель двух натуральных чисел x и y.
Решение. Обозначим через nod(x,y) – наибольший общий делитель x и y. Известно, что
(2)
На этих утверждениях базируется известный итеративный алгоритм Евклида, нахождения наибольшего общего делителя двух целых чисел. Внимательный взгляд на соотношения (2) приводит нас к убеждению, что фактически мы имеем рекурсивное определение функции nod(x,y). На языке Mathcad это надо было бы записать так.
![]()
Контрольные примеры.
![]()
Обобщим решенную задачу, составив программу-функцию, возвращающую наибольший общий делитель нескольких натуральных чисел ap (p=0..n-1, nі1), являющихся компонентами вектора v=(a0,a1,…,an-1)T.
Обозначим через nodd(a0,a1,…,an-1) – наибольший общий делитель чисел ap (p=0..n-1). Поскольку
nodd(a0,a1,…,an-1)=nod(nodd(a0,a1,…,an-2),an-1) ,
то соответствующая программа-функция, вычисляющая nodd(v) будет выглядеть так:

Контрольный пример.
![]()
- Наименьшее общее кратное
Задача 9. Составить программу-функцию, возвращающую наименьшее общее кратное натуральных чисел ap (p=0..n-1, nі2), являющихся компонентами вектора v=(a0,a1,…,an-1)T.
Решение. Обозначим через nok(a0,a1,…,an-1) – наименьшее общее кратное чисел ap (p=0..n-1). Известно, что
![]()
и
![]()
Поэтому соответствующую программу-функцию можно было бы записать так:

где nod(x,y) - функция нахождения наибольшего общего делителя натуральных x и y.
Контрольный пример.
![]()
Функцию nok() можно записать в следующей более компактной форме:

- Биномиальные коэффициенты
Задача 10. Составить программу-функцию вычисления биномиальных коэффициентов С(n,m), где n m - целые и 0ЈmЈn.
Решение. Известно, что
![]()
Отсюда и вытекает справедливость следующего рекурсивного определения С(n,m):

Обратите внимание на то, что здесь мы имеем рекурсию сразу по двум аргументам.
Опираясь на функцию C(n,m) как на подпрограмму, построим функцию binom(n,k), возвращающую для целого nі0 вектор из k последовательных биномиальных коэффициентов: С(n,0), C(n,1),…,C(n,k) (kЈn).
Решение данной задачи можно записать так:
![]()
Контрольные примеры.
![]()
Замечание. Для отыскания всех биномиальных коэффициентов при заданном n не обязательно вычислять binom(n,n). Учитывая, что C(n,k)=C(n,n-k), достаточно вычислить binom(n,(n-mod(n/2))/2).
И еще один способ вычисления биномиальных коэффициентов. Рекурсивная программа-функция tripas(n) вычисляет треугольник Паскаля, то есть значения величин C(i,j) для (0ЈiЈn , 0ЈjЈi), исходя из формул непосредственно определяющих и декомпозицию и базу:
![]()
![]()
Справа от функции просчитан контрольный пример для n=4.

Вычисления
по tripas(n)
реализуются
не более чем
за n
рекурсивных
обращений, при
этом общее
количество
операций сложения
не превосходит
величины
- Задача о Ханойских башнях
Рассмотрим следующую весьма популярную у студентов задачу.
Задача о Ханойских башнях. На одном из трех алмазных шпилей надето 64 круглых золотых диска. Диски имеют разные радиусы и расположены на шпиле в порядке убывания радиусов от основания к вершине. Трудолюбивые буддийские монахи день и ночь переносят диски с первого шпиля на второй, используя при необходимости и третий шпиль. При этом неукоснительно соблюдаются следующие правила.
· за один раз можно перемещать только один диск.
· больший диск нельзя располагать на меньшем.
· снятый диск необходимо надеть на какой-либо шпиль перед тем как будет снят другой диск.
Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Можно было бы подсчитать, что для решения задачи с 64 дисками потребуется 264 – 1 перемещений (около 1020). Поэтому, что касается конца света, то он произойдет по истечении пяти миллиардов веков, если считать, что один диск перемещается за одну секунду. Впрочем, и задачу и легенду для неё придумал в 1883 году математик Э. Люка. Это дает нам право отложить заботы о конце света в сторону и перейти к решению следующей задачи.
Задача 11. Составить рекурсивную программу-функцию, которая бы решала поставленную выше задачу о Ханойских башнях при количестве дисков, равном n (n = 1, 2, …).
Решение. Введем имена для шпилей: a , b , c. Пусть hanoi(n, a, b, c) искомая функция, возвращающая последовательность перемещений дисков с a на b c использованием c по вышеописанным правилам. При n = 1 решать задачу мы умеем. Необходимо просто произвести операцию “переместить a ® b”. Предположим, что мы умеем решать эту задачу для n – 1 диска. Тогда общая схема рекурсии могла бы выглядеть следующим образом.

Иными словами, переместим n – 1 диск с a на с. Далее, переместим один оставшийся диск с a на b и, наконец, переместим n – 1 диск с c на b. Что нам мешает реализовать эту схему на языке программирования Mathcad? По-видимому то, что в процессе вычисления функции hanoi(n, a, b, c), мы не в состоянии организовать вывод сообщений типа “переместить a ® b”. Остается одно средство. Организовать рекурсивные обращения так, чтобы все подобные ходы-перемещения запоминались в массиве, который и будет возвращаться функцией hanoi(n, a, b, c).
Вот один из возможных вариантов определения функции hanoi():

Функция возвращает матрицу размера kґ2, в каждой строчке которой фиксируется перемещение одного диска (откуда, куда). Величина k равна общему количеству перемещений.
Контрольный пример. При трех дисках с именами шпилей 1, 2 и 3 получаем следующее решение:

- Экзотические средние
Теперь решим задачу, связанную с экзотическими средними. Рассмотрим два положительных числа а0 и b0 и составим их среднее арифметическое и среднее геометрическое. Продолжим этот процесс и, если числа an и bn уже построены, то определим an+1 и bn+1 следующим образом:
(3)
Известно, что последовательности {an} и {bn} стремятся к общему пределу и, следуя Гауссу, его называют средним арифметико-геометрическим исходных чисел а0 и b0.
Задача 12. Составить рекурсивную программу-функцию, по которой для неотрицательных чисел a и b можно было бы приближенно вычислять их арифметико-геометрическое среднее.
Решение. Параметрами задачи естественно считать исходные величины a, b и количество итераций n по формулам (3). Рекурсию организуем по n, a решением задачи будем считать матрицу (an, bn). Построить соответствующую функцию несложно и выглядеть она может, например, т

Контрольные примеры.
age(100,30,3)=[59.77675556213139 59.77665550389991],
age(100,30,5)=[59.77670553300519 59.77670553300519].
Снова отправляясь от двух положительных чисел а0 и b0 станем последовательно составлять средние арифметические и средние гармонические:
(4)
Известно, что последовательности {an} и {bn}, строящиеся по рекуррентным формулам (4), стремятся к общему пределу. Его называют средним арифметико-гармоническим исходных чисел а0 и b0. Оказывается, что среднее арифметико-гармоническое двух чисел совпадает с их средним геометрическим.
Задача 13.
Составить
рекурсивную
программу-функцию,
по которой для
неотрицательных
чисел a и
b можно было
бы приближенно
вычислять их
арифметико-гармоническое
среднее, то
есть приближенное
значение
![]()
Решение. Как и в предыдущем случае, параметрами задачи естественно считать исходные величины a, b и количество итераций n по формулам (4). Рекурсию организуем по n, a решением задачи будем считать матрицу (an, bn). Соответствующая функция может выглядеть так:

Контрольный пример.
aga(100,20,7)=[44.7213595499958 44.7213595499958],
![]()
- Итерация функции в точке
Задача 14. Составить программу для нахождения n-ой итерации (n = 0, 1, 2,…) функции F(x) в точке a.
Решение. В соответствии с условиями задачи программа должна вычислять значение выражения вида F(F(F…F(a)…)) при n-кратном использовании операции F. Функция iter(F,a,n) решает поставленную задачу.
![]()
Контрольный пример.

- Вещественный корень f(x)
Задача 15. Пусть функция f(x) вещественной переменной x непрерывна на отрезке [a, b] и f(a)Чf(b) Ј 0. Составить программу нахождения на [a, b] какого-либо вещественного корня f(x).
Решение. Во первых, при перечисленных выше условиях по крайней мере один корень f(x) на [a, b] существует. Во вторых, договоримся о том, как понимать слова “найти корень”? Будем считать, что корень ищется с точностью e > 0, то есть должен быть найден отрезок [a, b] (b – a < 2Чe), на котором корень имеется. Тогда в качестве приближенного значения корня может быть взята точка x0 = (b + a)/2.
Для отыскания решения многих задач часто используется метод дихотомии, называемый также методом последовательного деления пополам, бисекции или вилки. В некоторых ранее рассмотренных задачах мы уже сталкивались с этим методом. В нашем случае, когда ищется корень уравнения, суть его в следующем. Пусть e > 0 задано. Делим отрезок [a, b] точкой с=(b+a)/2 на две равные части и в качестве нового отрезка [a, b] берем ту из его половин, для которой снова f(a)Чf(b) Ј 0 и т.д. Ясно, что на некотором шаге будем иметь отрезок [a, b] такой, что b – a < 2Чe и f(a)Чf(b) Ј 0. Следовательно, приближенное решение найдено и оно равно (b + a)/2.
А как записать предложенный алгоритм с использованием рекурсии? Оказывается все достаточно просто.

Контрольные примеры.
1. y(x):= x3dicho(y, -1, 1, 0.01) = -0.008
f(u)=uЧ(u + sin(u) – 3)Чexp(cos(u))
dicho(f, 1, 3, 0.0001) = 2.18f(2.18)=0
Задача 16. Пусть функция f(x) вещественной переменной x непрерывна на отрезке [a, b]. Составить программу нахождения на [a, b] любого вещественного корня f(x). При отсутствии корней, должно быть выдано значение Ґ (10307).
Решение. Отличие постановки этой задачи от предыдущей в том, что здесь априори ничего неизвестно о знаках функции на концах отрезка и, следовательно, корней f(x) уже может и не быть. Однако метод дихотомии с успехом может быть применен и в данном случае. Соответствующий алгоритм может быть записан так.

Контрольные примеры.
Рассмотрим функции примеров из предыдущей задачи. Имеем:
dichot(y,1,7,0.001)=10307 , dichot(f,2.17,3,0.0001)=2.18 .
Периодическое продолжение
Задача 17. Составить программу, которая для функции g(x), определенной при x О [a,b), строит функцию peri(g,a,b,x), являющуюся периодическим продолжением g(x) на всю действительную ось c периодом w = b – a.
Решение. Нам, очевидно, требуется определить функцию следующего вида.

На языке Mathcad это будет выглядеть практически так же:

Заметим, что при x находящемся вдали от промежутка [a,b) вычисления значения функции peri() требует значительного количества рекурсивных вызовов. Происходит это по той причине, что за один такой вызов мы продвигаемся в направлении [a,b) лишь на расстояние w=b-a.
Значительно эффективней проводятся вычисления по функции F(g,x,a,b) также являющейся периодическим продолжением g(x) на всю числовую ось.

Контрольные примеры.
1. Пусть y(x) = x2Чsin(x). Тогда:
peri(y,1,0,2) = 0.841 peri(y,3,0,2) = 0.841
peri(y,-1,0,2) = 0.841 peri(y,1001,0,2)=0.841
2. На рис. 3.4 изображен график функции H(t), являющейся периодическим продолжением функции y(x)= x2Чsin(x) для x О [-10, 0). H(t) построено с помощью программы-функции F(), а график выведен на промежутке [-10,20) с шагом h=0.1.
t:= -10,-9.9..20 H(t):=perri(y,t,-10,0)

Рис. 3.4 Периодическое продолжение функции y(x)= x2Чsin(x)
для x О [-10, 0).
- Функция Аккермана
Задача 18. Пусть n и m целые неотрицательные числа. Написать программу, вычисляющую классическую в теории рекурсии функцию Аккермана:
(5)
Решение. Вычислить функцию Аккермана, исходя непосредственно из определения (5), удается лишь для некоторых малых n и m. Связано это со сложностью и необычностью рекурсивного определения. В общем случае не только ak() вычисляется через ak(), но и второй из аргументов функции также требует рекурсивного вызова ak(). Соответствующая программа-функция может быть записана так:

Контрольные примеры.
![]()
Следующий вариант программы для вычисления функции Аккермана включает в себя лишь один рекурсивный вызов:

Замечание. Для m=0..4 справедливы соотношения [5, с. 69]:

Эти формулы могут оказаться полезными при построении контрольных примеров для отладки новых более эффективных вариантов программ вычисления функции Аккермана.
В работе [5, c. 256-260] приведен нерекурсивный вариант алгоритма вычисления значений функции Аккермана.
- Функция Маккарти
Задача 19. Функция Маккарти. Показать, что для приведенной ниже рекурсивной программы-функции
![]()
при целочисленных значениях n справедлива формула:
(6)
Решение. Относительно параметра n возможны три случая:
n > 100,90Ј n Ј100, -Ґ < n<90.
В первом из них в силу базы рекурсии следует, что makkarti(n)=n-10. Во втором случае:
![]()
Наконец, всякое начальное n<90 в соответствии с декомпозицией через конечное число рекурсивных вызовов приводит ко второму случаю. Отсюда опять makkarti(n)=91. Таким образом (6) справедливо во всех случаях.
Заметим, что из проведенных рассуждений вытекает, что рассматриваемая функция может быть определена более просто, например, так:
![]()
- Функция Кадью
Задача 20. Показать, что для приведенной ниже рекурсивной программы-функции
![]()
при целочисленных значениях x справедлива формула:
(7)
Решение. При y=0 и z=1 имеем z=y!. Далее из характера декомпозиции функции cadiou() ясно, что z=y! остается инвариантом в ходе рекурсивных вызовов. Вместе с условием завершения x=y это и дает z=x! и (7) установлено.
- Количество делителей
Задача 21.Количество делителей. Составить программу-функцию подсчета для натурального числа n количества всех его делителей.
Решение. Перейдем к более общей задаче. Подсчитаем для натурального числа n количества всех его делителей, меньших или равных заданному натуральному числу x. Пусть dn(n) и dnx(n,x) - соответственно функции для решения исходной и обобщенной задач. Очевидно, что dn(n)=dnx(n,n).
Рекурсивную функцию dnx(n,x), по которой последовательно подвергаются испытанию на делители n все числа от 1 до x включительно, можно определить так:
![]()
![]()
Контрольные примеры.
![]()
Далее, если n і2 и dn(n)=2, то число n – простое. Однако проверка n на простоту этим способом весьма неэкономна.
- Простые числа
Задача 22. Составить программу-функцию проверяющую, является ли заданное натурально число n простым?
Решение. Пусть рекурсивная функция isprim(n) является решением задачи и

Дальнейшие рассуждения являются иллюстрацией использования классического приема “вложения” (Дж. Маккарти, 1962). Перейдем к рассмотрению следующей обобщенной задачи. Пусть a, b, n - натуральные числа и 2ЈaЈbЈn. Верно ли, что заданное n не делится ни на одно целое из отрезка [a, b]? Пусть эту задачу решает функция
Ниже приведено три рекурсивных варианта реализации этой функции. По первому из них проверке на делитель n последовательно подвергаются числа: a, a+1, … , b; по второму - эти же числа в обратном порядке и, наконец, по третьему - a, b, a+1, b-1, … .



Контрольные примеры.
![]()
Далее,
натуральное
число nі2
является простым,
если оно не
имеет делителей
на отрезке
,
поэтому характеристическая
функция isprim(n)
через функцию
nodiv(n,a,b)
может быть
выражена так:
![]()
Контрольные примеры.
![]()
Задача 23. Составить программу-функцию pi(x), которая подсчитывает количество простых чисел, не превосходящих заданное число x.
Решение. С помощью функций nodiv() или isprim() рекурсивный вариант функции pi(x) строится достаточно просто, исходя из такого декомпозиционного утверждения. Количество простых чисел, не превосходящих x, составляется из количества простых чисел меньших или равных x-1 плюс значение функции isprim(x). Поэтому:
![]()
Контрольные примеры.
![]()
Задача 24. Составить программу pn(n), которая вычисляет n-ое простое число (n – натуральное).
Решение. Предварительно напишем рекурсивную подпрограмму-функ-цию minp(m) нахождения наименьшего простого числа, большего или равного m (m – натуральное число). Сделать это можно, например, так:
![]()
Контрольные примеры.
![]()
Тогда искомая функция pn(n) может быть определена так:
![]()
Контрольные примеры.
![]()
- Схема Горнера
Задача 25. Составить программу-функцию вычисления значений многочлена по схеме Горнера.
Решение. Пусть f(x) многочлен с вещественными или комплексными коэффициентами и v – вектор этих коэффициентов:
(8)
(9)
Вычисление f(x) в точке x по схеме Горнера проводится от самых внутренних скобок и далее в соответствии с представлением:
![]()
Отсюда ясно, как записать рекурсивный и не рекурсивный варианты алгоритмов вычисления f(x). Нас интересует только первый из них. Параметрами задачи можно считать вектор v и точку a для вычисления f(a). Тривиальный случай – многочлен нулевой степени: f(a) = a0. Декомпозиция получается из указанной выше расстановки скобок в записи f(x). Соответствующая программа-функция выглядит, например, так.

Контрольные примеры.
![]()
Замечание. Параметр n – это константа, равная степени многочлена. По вектору v она определяется однозначно. Однако в каждом рекурсивном вызове проводится перевычисление n. Избежать лишней вычислительной работы в подобных ситуациях можно двумя способами. Или определять такие константы заранее вне текста программы-функции или передавать их значения через дополнительные аргументы функции.
- Деление многочлена на двучлен
Задача 26. Составить программу-функцию, по которой для многочлена (8) с коэффициентами, составляющими вектор (9) и двучлена x-x0 (x0 - вещественное или комплексное число), вычисляется вектор c:
![]()
такой, что
![]()
и
![]()
Решение. Если в соотношении, связывающем многочлены f(x) и q(x), осуществить приведение к общему знаменателю и приравнивание коэффициентов при одинаковых степенях x, то для определения компонент вектора c получим следующую систему линейных уравнений.
![]()
Отсюда вытекает,