Все существующие программы. Часть 5

В прошлый раз: Мы явно уменьшили задачу размером k, к нескольким задачам размера, меньшего, чем k-1, так что эта задача является отличным кандидатом для рекурсивного решения. Так ведь?

Нет, не так. (Слово «явно» было предательским.) Вспомните о трех вещах, необходимых для рекурсивного решения. Во-первых, должен быть способ свести задачу некоторого размера к похожей задаче меньшего размера. Во-вторых, должен быть путь объединения решений меньшего размера в решение задачи большего размера. И в-третьих, минимально возможная задача должна иметь нерекурсивное решение; рекурсия должна когда-то завершиться.

Есть ли у нас все это? Кажется, что да, но давайте рассмотрим другой пример. Ранее мы обсуждали грамматику для арифметического сложения. Давайте в нее внесем небольшое изменение:

S: N | S P
P: + N
N: 1 | 2 | 3

Я надеюсь, вы согласитесь, что это абсолютно тот же самый язык, просто с несколько другой грамматикой. Теперь давайте подумаем над тем, как мы ответим на вопрос «какими будут все строки этой грамматики, формы S, с тремя терминальными символами? Мне нужна краткая форма записи этого, поэтому пусть S<3> означает именно это. Тогда X<n>Y<m> будет означать, что это «набор строк, который является комбинацией всех возможных строк X<n>, за которыми следуют все возможные строки Y<m>».

Так что же из себя представляет S<3>? Это комбинация N<3>, S<0>P<3>, S<1>P<2>, S<2>P<1> и S<3>P<0>.

Ой-ой-ой. Мы не выполняем первое условие; мы сводим задачу: «какими будут все строки размера три, которые соответствуют S» к набору задач, которые сами требуют решения! На самом же деле подзадача S<3>P<0> решаема, если мы знаем, что можем пропустить ее, поскольку не существует таких строк формы P с нулевым количеством терминальных символов. Но как мы об этом узнаем? В этом конкретном случае, очевидно, что решение P никогда не дает NIL, но в общем случае мы узнать об этом не можем.

Черт возьми, да мы не можем удовлетворить также и третьему условию; решение задачи S<0> сводится к решению двух задач N<0> и S<0>P<0>, что является большей задачей!

Можно добиться некоторого прогресса, если мы сумеем комментировать нашу грамматику, скажем так: «кстати, я знаю, что это правило всегда дает хотя бы один терминальный символ, так что вам не нужно рассматривать нулевые случаи». Этот вариант выполнимый, но не очень приятный.

Есть ли другой путь?

В следующий раз: Конечно, есть.

Оригинал статьи