Более сложные случаи рекурсии

Пусть функция f с натуральными аргументами и значениями определена рекурсивно условиями $\begin{displaymath} \begin{array} {rcl} f(0)&\!\!\!=\!\!\!&a,\\ \noalign{\vskip3pt} f(x)&\!\!\!=\!\!\!&h(x, f(l(x))) \quad (x\gt),\end{array}\end{displaymath}$ где a -- некоторое число, а h и l -- известные функции. Другими словами, значение функции f в точке x выражается через значение f в точке l(x) . При этом предполагается, что для любого x в последовательности $\begin{displaymath} x,\ l(x),\ l(l(x)),\ \ldots\end{displaymath}$ рано или поздно встретится 0.

Если дополнительно известно, что для всех x , то вычисление f не представляет труда: вычисляем последовательно f(0) , f(1) , f(2) , $\ldots\,$ .

$\scriptstyle{\blacktriangleright}$ 8.3.1. Написать нерекурсивную программу вычисления f для общего случая.

Решение. Для вычисления f(x) вычисляем последовательность $\begin{displaymath} l(x),\ l(l(x)),\ l(l(l(x))),\ \ldots\end{displaymath}$ до появления нуля и запоминаем ее, а затем вычисляем значения f в точках этой последовательности, идя справа налево. $\scriptstyle\blacktriangleleft$

Еще более сложный случай из следующей задачи вряд ли встретится на практике (а если и встретится, то проще рекурсию не устранять, а оставить). Но тем не менее: пусть функция f с натуральными аргументами и значениями определяется соотношениями $\begin{displaymath} \begin{array} {rcl} f(0)&\!\!\!=\!\!\!& a,\\ \noalign{\vski... ...&\!\!\!=\!\!\!& h(x, f(l(x)), f(r(x))) \quad (x\gt),\end{array}\end{displaymath}$ где a -- некоторое число, а l , r и h -- известные функции. Предполагается, что если взять произвольное число и начать применять к нему функции l и r в произвольном порядке, то рано или поздно получится .

$\scriptstyle{\blacktriangleright}$ 8.3.2. Написать нерекурсивную программу вычисления f .

Решение. Можно было бы сначала построить дерево, у которого в корне находится x , а в сыновьях вершины i стоят l(i) и r(i) -- если только i не равно нулю. Затем вычислять значения функции, идя от листьев к корню. Однако есть и другой способ.

Обратной польской записью (или постфиксной записью) выражения называют запись, где знак функции стоит после всех ее аргументов, а скобки не используются. Вот несколько примеров: $\begin{displaymath} \begin{array} {llllllll} f(2) & 2&f& & & & & \\ f(g(2)) & ... ...t&s& & & \\ s(2, u(2, s(5,3))\qquad & 2&2&5&3&s&u&s\end{array}\end{displaymath}$ Постфиксная запись выражения позволяет удобно вычислять его с помощью стекового калькулятора. Этот калькулятор имеет стек, который мы будем представлять себе расположенным горизонтально (числа вынимаются и кладутся справа), и клавиши -- числовые и функциональные. При нажатии на клавишу с числом это число кладется в стек. При нажатии на функциональную клавишу соответствующая функция применяется к нескольким аргументам у вершины стека. Например, если в стеке были числа

$\begin{displaymath} 2\ 3\ 4\ 5\ 6\end{displaymath}$

и нажата функциональная клавиша s , соответствующая функции от двух аргументов, то в стеке окажутся числа

$\begin{displaymath} 2\ 3\ 4\ s(5,6)\end{displaymath}$ -.5mm Перейдем теперь к нашей задаче. В процессе вычисления значения функции f мы будем работать со стеком чисел, а также с последовательностью чисел и символов f, l, r, h, которую мы будем интерпретировать как последовательность нажатий клавиш на стековом калькуляторе. Инвариант такой:

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

Пусть нам требуется вычислить значение f(x) . Тогда вначале мы помещаем в стек число x , а последовательность содержит единственный символ f. (При этом инвариант соблюдается.) Далее с последовательностью и стеком выполняются такие преобразования:

$\begin{displaymath} \footnotesize \setlength {\arraycolsep}{.8em} \begin{array... ...x\ {\hbox{\tt r}}\ {\hbox{\tt f}}\ {\hbox{\tt h}}\ P\end{array}\end{displaymath}$ Здесь x , y , z -- числа, X -- последовательность чисел, P -- последовательность чисел и символов f, l, r, h. В последней строке предполагается, что $x\ne 0$ .Эта строка соответствует равенству

$\begin{displaymath} f(x) = h(x, f(l(x)), f(r(x))).\end{displaymath}$ Преобразования выполняются, пока последовательность не станет пуста. В этот момент в стеке окажется единственное число, которое и будет ответом. $\scriptstyle\blacktriangleleft$

Замечание. Последовательность по существу представляет собой стек отложенных заданий (вершина которого находится слева).

pvv
1/8/1999