Когда увидел прогу старой доброй Ханойской башни в теме "Рекурсия", не мог не вспомнить, про задачку, которую некоторым продвинутым прикладникам у нас давали на годовом экзамене на 1 курсе: написать её НЕрекурсивную реализацию. Некоторые, в общем-то, неглупые люди тогда сидели над ней часа по три, так и не решив.
У нас экзамен был после них, и я зарнее написал эту прогу(хотя так и не досталась). Поднапрягся и за полчаса набросал алгоритм. Но, скажу я, это было для меня тогда далеко не очевидно, да и теперь не знаю, сколько бы у меня ушло.
Ниже мой код. Всего строчек 15-20. Но очень советую - ради интереса, попробуйте сначала сами реализовать его - очень неплохая разминка для мозгов!
За сколько времени получится?
Вообще , Ханойская башня, числа Фибоначчи и т. п. - задачи, для который рекурсивное решение "само напрашивается", наиболее понятно, удобно и быстро пишется. Но попробуйте-ка запустить рекурсивную и итерационную прогу той же Башни для большого числа колец, да хотя бы 10-15. В данном случае, итерация хотя во много раз сложнее, но и во много раз быстрее.
Есть ещё рекурсивные АТД, например, деревья. Для них, хотя и с трудом, то тоже можно писать итерационные процедуры, скажем, поика и заполнения.
Я одном своём проекте столкнулся с прямой необходимостью этого - просто при небольшом увеличении одного параметра прога может выполняться больше часа, а потом вылететь от переполнения. Так что рано или поздно этому придётся учиться каждому.
Предлагаю: присылайте интересные итерационные варианты рекурсивных прог, а главное, идеи относительно методов перехода от рекурсии к итерации.
У меня есть некоторые мысли, например, метод выделения инвариантов (которым, в принципе, и воспользовался в HanoyTower).
Да, здорово!
А я тоже решил переделать рекурсивную процедуру!
(в теме рекурсия- я выложил процедуру возведения в степень, вот ее не рекурсивный вариант (работает быстрее, т.к. рекурсия - медленная штука!)
Oleg_Z, говоря по правде рекурсия в таком методе возведения в степень абсолютно лишняя.
Возведение в степень, используемое при арифметике с большими числами (здесь хоть рекурсия нужна).