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

  •  
      Пусть функция f с натуральными аргументами и значениями определена рекурсивно условиями
      f(0) = a,
      f(x) = h(x, f(l(x))),

      где a - некоторое число, а h и l - известные функции. Другими словами, значение функции f в точке x выражается через значение f в точке l(x). При этом предполагается, что для любого x в последовательности
      x, l(x), l(l(x)),...
      рано или поздно встретится 0.

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

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

      Решение. Для вычисления f(x) вычисляем последовательность
      l(x), l(l(x)), l(l(l(x))),...

      до появления нуля и запоминаем ее, а затем вычисляем значения f в точках этой последовательности, идя справа налево.

      Еще более сложный случай из следующей задачи вряд ли встретится на практике (а если и встретится, то проще рекурсию не устранять, а оставить). Но тем не менее: пусть функция f с натуральными аргументами и значениями определяется соотношениями
      f(0) = a,
      f(x) = h(x, f(l(x)), f(r(x))),

      где a - некоторое число, а l, r и h - известные функции. Предполагается, что если взять произвольное число и начать применять к нему функции l и r в произвольном порядке, то рано или поздно получится 0.

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

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

      "Обратной польской записью" (или "постфиксной записью") выражения называют запись, где знак функции стоит после всех ее аргументов, а скобки не используются. Вот несколько примеров:
      f(2) 2 f
      f(g(2)) 2 g f
      s(2,t(7)) 2 7 t s
      s(2, u(2, s(5,3)) 2 2 5 3 s u s

      Постфиксная запись выражения позволяет удобно вычислять его с помощью "стекового калькулятора". Этот калькулятор имеет стек, который мы будем представлять себе расположенным горизонтально (числа вынимаются и кладутся справа), и клавиши - числовые и функциональные. При нажатии на клавишу с числом это число кладется в стек. При нажатии на функциональную клавишу соответствующая функция применяется к нескольким аргументам у вершины стека. Например, если в стеке были числа
      2 3 4 5 6
      и нажата функциональная клавиша s, соответствующая функции от двух аргументов, то в стеке окажутся числа
      2 3 4 s(5,6)

      Перейдем теперь к нашей задаче. В процессе вычисления значения функции f мы будем работать со стеком чисел, а также с последовательностью чисел и символов "f", "l", "r", "h", которую мы будем интерпретировать как последовательность нажатий клавиш на стековом калькуляторе. Инвариант такой:
      если стек чисел представляет собой текущее состояние
      стекового калькулятора, то после нажатия всех клавиш
      последовательности в стеке останется единственное
      число, и оно будет искомым ответом.

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

      X x P X x P
      X x l P X l(x) P
      X x r P X r(x) P
      X x y z h P X h(x,y,z) P
      X 0 f P X a P
      X x f P X x x l f x r f h P

      Здесь x, y, z,.. - числа, X - последовательность чисел, P - последовательность чисел и символов "f", "l", "r", "h". В последней строке предполагается, что x не равно 0. Эта строка соответствует равенству
      f(x) = h(x, f(l(x)), f(r(x))).

      Преобразования выполняются, пока последовательность не станет пуста. В этот момент в стеке окажется единственное число, которое и будет ответом.

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

Другие записи

10.06.2016. 8.1. Таблица значений (динамическое программирование)
  Для универсальных языков программирования (каковым является паскаль) рекурсия не дает ничего нового: для всякой рекурсивной программы можно написать эквивалентную программу без рекурсии. Мы не…