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

Пусть функция 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.

Если дополнительно известно, что $l(x) < x$ для всех 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