Иногда исходная задача естественным образом распадается на две или более вспомогательные родственные задачи так, что в совокупности, взаимно дополняя друг друга, они уже будут определять вполне просматриваемую косвенную рекурсию.
Рассмотрим пример, связанный с экзотическими средними. Пусть
a0 и b0 - два положительных числа (a0>b0). Составим их среднее арифметическое и среднее геометрическое. Продолжим этот процесс рекурсивно. Если числа an и bn уже построены, то определим an+1 и bn+1 следующим образом:Можно показать, что
a0>an>an+1>bn+1>bn>b0 (n=1, 2, …). Откуда вытекает, что обе последовательности (an) и (bn) с двух разных сторон монотонно стремятся к общему пределу, и, следуя Гауссу, его называют средним арифметико-геометрическим исходных чисел a0 и b0. Таким образом, при любом заданном n (n=0, 1, 2, …) числа an и bn служат приближениями сверху и снизу для среднего арифметико-геометрического a0 и b0. И для их нахождения можно воспользоваться парой рекурсивных функций sa(a,b,n) и sq(a,b,n) (язык программирования QBasic). Синтаксис и семантика функций sa(a,b,n) и sq(a,b,n) достаточно ясны и прозрачны. В головной программе проводится объявление этих функций, организуется ввод фактических значений их формальных параметров и, наконец, выводятся результаты вычислений.
DECLARE FUNCTION sa (a, b, n)DECLARE FUNCTION sg (a, b, n) INPUT a, b, n PRINT sa(a, b, n), sg(a, b, n) |
FUNCTION sa (a, b, n)IF n = 0 THEN sa = a ELSE sa = (sa(a, b, n - 1) + sg(a, b, n - 1)) / 2 END IF END FUNCTION |
FUNCTION sg (a, b, n)IF n = 0 THEN sg = b ELSE sg = SQR(sa(a, b, n - 1) × sg(a, b, n - 1)) END IF END FUNCTION |
Поскольку, явно проглядываемая в постановке задачи, косвенная рекурсия не может быть реализована в среде Mathcad, все программы были написаны на языке Qbasic. Впрочем, можно было бы обнаружить и прямой рекурсивный алгоритм решения задачи. Однако сделать это не так то просто, хотя его программная реализация на языке программирования Mathcad в виде функции
age(a,b,n) выглядит удивительно компактно и элегантно:Контрольные примеры:
age(100, 30, 3) = [59.77675556213139 59.77665550389991],
age(100, 30, 5) = [59.77670553300519 59.77670553300519].