К вопросу о конце света
Вернемся к вопросу о конце света. Время, необходимое программе для переноса башни, состоящей из n дисков, приблизительно пропорционально 2n. Можно сказать, что этот алгоритм имеет экспоненциальную сложность в смысле временных затрат. Алгоритмы этого типа применять нежелательно, т.к. даже для вполне разумных значений входных данных время выполнения может становиться слишком большим.
Допустим, что ЭВМ может вычислить одну переменную за 1/1000000 долю секунды. Даже при такой скорости расчета переноса башни из 64 дисков потребуется около миллиона лет.
До сих пор мы могли быть уверены, что при обработке действий, указанных в алгоритме, никаких проблем не возникнет. В частности, могли быть уверены, что число операций не превзойдет некоторого фиксированного максимального числа. Теперь это уже не так: чтобы быть уверенным, что мы своим "самовызовом" не устроили circulus vitiosus (порочный круг), мы должны для рекурсивных алгоритмов всегда проводить доказательство окончания.
Например, известная шутка: "Как поймать стаю львов в пустыне?" Ответ: надо поймать одного льва и тем самым свести задачу к более простому случаю. Доказательство здесь очевидно, если каждый лев может быть пойман за конечное время.
При анализе рекурсивной программы возникает, как обычно, два вопроса:
(а) почему программа заканчивает работу?
(б) почему она работает правильно, если заканчивает работу?
Для (б) достаточно проверить, что (содержащая рекурсивный вызов) программа работает правильно, предположив, что вызываемая ею одноименная программа работает правильно. В самом деле, в этом случае в цепочке рекурсивно вызываемых программ все программы работают правильно (убеждаемся в этом, идя от конца цепочки к началу).
Чтобы доказать (а), обычно проверяют, что с каждым рекурсивным вызовом значение какого-то параметра уменьшается, и это не может продолжаться бесконечно.
Чтобы рекурсивные процедуры не делали вызовы бесконечно, необходимо проверять условия окончания вызовов, т.е. какая-то величина должна изменяться и, в конце концов, придти к тому своему значению, когда очередной вызов не будет сделан.
В процедуре расчета факториала это параметр i, который уменьшается при каждом очередном вызове на 1 и в результате станет равным 1. В задаче про Ханойские башни — это число колец, которые необходимо перенести и т.д.
Но для рекурсии этого мало!!!
Очень важно понимать, как ЭВМ выполняет рекурсивные вызовы, т.к. рекурсия не только полезна, но и опасна. У нас есть "доказательство" того, что рано или поздно вызовы прекратятся, но при этом не возникает ни какого представления о том, какие действия и как будут выполняться. В этом и состоит опасность.
Выясним, что значит "рано или поздно". Ведь может оказаться, что полученный алгоритм ужасающе не эффективен (например, может выполняться сотни лет).
Рассмотрим этот факт на примере вычисления последовательности чисел Фибоначчи. Пусть необходимо найти Ф(45).
По представленной ранее формуле: Ф(n) = Ф(n-1) + Ф(n-2).
Для нахождения Ф(45) будут выполнены вызовы Ф(44) и Ф(43). Тогда из Ф(44) надо будет вызывать Ф(43) и Ф(42). При вычислении Ф(43) вызываются Ф(42) и Ф(41) и т.д.
Т
аким
образом, получаем:
Из представленной схемы видно, что Ф(42) вызывался уже 3 раза (в разных местах картинки). Когда дойдем до Ф(1) и Ф(2), которые вычисляются явно, у нас будет уже больше миллиарда разных Ф(…). А на все эти манипуляции тратится память, время на постоянное "откладывание" выполнения действий и т.п.
Таким образом, при составлении рекурсивных алгоритмов надо представлять, как он будет выполняться — не возникнет ли эффекта удвоения (утроения и т.д.) объема работы.
Если рекурсивный алгоритм вызывает сам себя только один раз (в одном месте), то, как правило, это не опасно. Но если несколько, то потенциально такая рекурсия очень опасна.
Подведем итоги. Рекурсия — это несколько экзотический, потенциально опасный, но иногда весьма полезный метод алгоритмизации. Существуют задачи, которые легко решаются рекурсивно и которые без рекурсии решить очень трудно (например, составить алгоритм обхода конем шахматной доски; конь должен побывать в каждой клетке ровно по одному разу).