От рекурсии к итерации, Достоинства и недостатки Опции

[Atos]

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

Вообще , Ханойская башня, числа Фибоначчи и т. п. - задачи, для который рекурсивное решение "само напрашивается", наиболее понятно, удобно и быстро пишется. Но попробуйте-ка запустить рекурсивную и итерационную прогу той же Башни для большого числа колец, да хотя бы 10-15. В данном случае, итерация хотя во много раз сложнее, но и во много раз быстрее.
Есть ещё рекурсивные АТД, например, деревья. Для них, хотя и с трудом, то тоже можно писать итерационные процедуры, скажем, поика и заполнения.
Я одном своём проекте столкнулся с прямой необходимостью этого - просто при небольшом увеличении одного параметра прога может выполняться больше часа, а потом вылететь от переполнения. Так что рано или поздно этому придётся учиться каждому.

Предлагаю: присылайте интересные итерационные варианты рекурсивных прог, а главное, идеи относительно методов перехода от рекурсии к итерации.
У меня есть некоторые мысли, например, метод выделения инвариантов (которым, в принципе, и воспользовался в HanoyTower).

Код

                        program HanoyTower;
type TInt=longint;
procedure Tower(n:TInt);
var m,k,l,s:TInt;
    iz,v,c,x:byte;
begin
n:=longint(round(exp(n*ln(2))))-1;
for m:=1 to n do
  begin
  iz:=1; c:=2; v:=3; k:=1; l:=n; s:=(k+l) div 2;
  repeat
  if m<s then begin x:=v;  v:=c;  c:=x; l:=s-1; end;
  if m>s then begin x:=iz; iz:=c; c:=x; k:=s+1; end;
  if m=s then begin writeln(iz,'-',v); break; end;
  s:=(k+l) div 2;
  until 2*2=5;
  end;
end;

var n:TInt;
begin
n:=4;
Tower(n);
readln;
end.

+
см. Ханойские башни.

[zx1024]

Oleg_Z, говоря по правде рекурсия в таком методе возведения в степень абсолютно лишняя.
Возведение в степень, используемое при арифметике с большими числами (здесь хоть рекурсия нужна).

Код

function POW (a : real; n : integer) : real;
var b : real;
begin
 if n = 1 then
   POW := a
 else begin
   b := POW (a, n shr 1);
   if (n and 1) = 0 then
     POW := b*b
   else
     POW := b*b*a
 end;
end;

Без рекурсии

Код

function POW (a : real; n : integer) : real;
var b, c : real;
begin
 c := a;
 b := 1;
 while n > 1 do
 begin
   if (n and 1) = 1 then
     b := b * c;
   n := n shr 1;
   c := c * c;
 end;
 POW := b * c
end;