BASIC APASCALADO IV - A vinganca da recursividade!

Como resolver o problema das Torres de Hanoi iterativamente? 
Bem, pode-se deduzir um algoritmo relativamente simples...

Suponhamos que o número de discos é impar e desenhemos  uma  tabela  com  quatro  colunas:  
na primeira  coluna  escrevemos,  alternadamente,  os valores  "1" e "0";  na segunda coluna 
 escrevemos "1", "2", "3", "1", "2", "3", "1"... ; na terceira coluna,  escrevemos o numero das
 pilhas  do ultimo movimento;  e  na quarta,  escrevemos  o movimento actual. Vejamos...

         13
  1 1 13 12
  0 2 12 32 
  1 3 32 13 
  0 1 13 21 
  1 2 21 23 
  0 3 23 13 
  1 1 13 12

Quando aparece  um "0"  na primeira  coluna, basta juntar  o valor da coluna 2.  
Quando aparece um "1"  na primeira coluna,  em principio há dois movimentos  possiveis  mas, 
 só  um é legal.  Se pensarem um bocado, descobrem a sequência disto. 

Como estão a ver, isto não é nada agradável. Num programa recursivo, basta descrever como
sao feitos  os movimentos  (espero que  já saibam como é que funcionam as Torres de Hanoi!).  
Mover N discos da pilha 1 para a pilha 3 é assim:
	1- Se vamos mover apenas um disco, fazemos o movimento da pilha 1 para a pilha 3.
	2- Caso contrario: movem-se N-1 discos, para a pilha auxiliar 2; 
           move-se o que ficou na pilha 1 para a pilha 3; 
           e depois, é só mover os N-1 discos que tinhamos colocado na pilha 2, para a pilha 3. 

Para compreender o programa é melhor estudar primeiro  a versao em PASCAL, que é mais simples. 
Podem tambem correr o programa BASIC no papel para ver o que se passa.

Como viram (ou deviam ter visto),  na versão iterativa precisamos indicar todos os passos de um 
algoritmo que calcule cada movimento, enquanto que, recursivamente apenas precisamos de descrever
 como as coisas  se devem passar, o próprio programa vai construindo a solução.

Moral da história: Viva a recursividade! Ficamos por aqui (uff!) no que  diz respeito
à recursividade em BASIC. Talvez um dia descubram alguma aplicação para ela...

Exercicío: Podem  acrescentar  duas  rotinas;  uma  para inicializar as  variaveis e  o ecran com 
o desenho das  pilhas de discos,  e outra para,  em  vez  de escrever  os  movimentos, actualizar
 o desenho das pilhas.  E, se ficarem aborrecidos com um programa recursivo, podem retirar as  rotinas
 de movimento, substituindo-as por um pedido ao utilizador! Ficam assim com um jogo curioso.

Nao  se esqueçam  que  a melhor  maneira para perceber um programa é reescrever ou extendê-lo.

No próximo artigo daremos uma vista de olhos no cúmulo da recursividade: a linguagem PROLOG.

{------------------------------------------------}

PROGRAM  hanoi (INPUT,OUTPUT);

VAR   numero_de_discos  :INTEGER;

  {------------------------------------------------} 

  PROCEDURE mover (n,fonte,auxiliar,destino:INTEGER); 
  BEGIN
    IF  n = 1
      THEN WRITELN('MOVER DE ',fonte,'PARA',destino) ELSE
        BEGIN
          mover(n-1,fonte,destino,auxiliar);
          WRITELN('MOVER DE',fonte,'PARA',destino); 
          mover(n-1,auxiliar,fonte,destino)
        END
  END;   {---  mover  -----------------------------}

BEGIN {-----  PROG  PRINCIPAL  ------------------} 
  WRITELN;
  WRITE  ('NUMERO DE DISCOS :  '); READLN(numero_de_discos);
  WRITELN;
  WRITE  ('NUMERO DE MOVIMENTOS NECESSARIOS =');
  WRITELN(POWER(2,numero_de_discos)-1);
  WRITELN;
  WRITELN('PARA ',numero_de_discos,' DISCOS'); 
  WRITELN('OS MOVIMENTOS SAO OS SEGUINTES: '); 
  WRITELN;
  mover(numero_de_discos,1,2,3)
END.  {-----  MAIN  PROG  -----------------------}


-------------------------------------------------5
  10 REM PROGRAM hanoi (Keyboard,Screen)
  20 REM (C) 1988 ZARSOFT Corporation
  30 REM Written by ZE OLIVEIRA
  40 REM BASIC apascalado / BASIC Sinclair
  60
 100 REM --- ROTINAS -----------------------------
 105 CLEAR
 110 LET main prog = 300
 115 LET ler arg = 350
 120 LET move = 400 
 125 LET move2 = 500 
 130 LET introduction = 700
 140 LET print move = 750
 150 LET push all = 800
 160 LET pop all = 850
 180 REM PREENCHER AS 3 LINHAS SEGUINTES - UTILIZAR A STACK PUBLICADA EM BASPAS2
 182 LET init stack = ... 
 184 LET push a = ...
 186 LET pop a = ...
 188 REM UTILIZAR A STACK PUBLICADA EM BASPAS2, MICROSE7E 60, FEVEREIRO-88 DE PREFERENCIA, A VERSAO OPTIMIZADA COM STRINGS 
 190
 200 REM --- VARIAVEIS PRINCIPAIS ----------------
 210 REM disks	numero de discos a mover
 220 REM lev	level (nivel de recursividade)
  		numero de discos a mover
 230 REM fonte	pilha fonte para movimento
 240 REM aux	pilha auxiliar
 250 REM dest	pilha destino
 260
 300 REM --- MAIN PROG ---------------------------
 310 GO SUB ler arg
 320 GO SUB introduction
 330 GO SUB move
 335 STOP
 340 REM main prog
 345
 350 REM --- LER ARG -----------------------------
 360 PRINT "NUMERO DE DISCOS = ";
 370 INPUT disks : PRINT disks
 380 RETURN
 385 REM ler arg
 390
 400 REM --- MOVE --------------------------------
 410 GO SUB init stack
 420 LET lev=disks: REM mover LEV discos
 422 LET fonte=1  : REM da pilha 1
 424 LET aux=2    : REM tendo 2 como auxiliar
 426 LET dest=3   : REM para a pilha 3
 430 GO SUB push all   : REM argumentos para move2
 440 GO SUB move2
 450 RETURN
 460 REM move
 490
 500 REM --- MOVE2 -------------------------------
 510 GO SUB pop all : REM receber argumentos
 520 IF lev=1 THEN GO SUB print move : RETURN
 530   GO SUB push all : REM guardar este nivel 
 540	REM argumentos para chamar move2:
 542	LET a=lev-1 : GO SUB push a
 544	LET a=fonte : GO SUB push a
 546	LET a=dest  : GO SUB push a
 548	LET a=aux   : GO SUB push a
 550	GO SUB move2
 560   GO SUB pop all : REM restaurar nivel
 570   GO SUB print move
 580   GO SUB push all : REM guardar este nivel
 590	REM argumentos para este procedimento:
 592	LET a=lev-1 : GO SUB push a
 594	LET a=aux   : GO SUB push a
 596	LET a=fonte : GO SUB push a
 598	LET a=dest  : GO SUB push a
 600	GO SUB move2
 610   GO SUB pop all : REM restaurar situacao
 620 RETURN
 630 REM move2
 640
 700 REM --- INTRODUCTION -----------------------
 710 PRINT "MOVIMENTOS NECESSARIOS: ";2^disks-1
 720 PRINT
 730 RETURN
 740 REM introduction
 745
 750 REM --- PRINT MOVE --------------------------
 760 PRINT "MOVER DE ";fonte;" PARA ";dest
 770 RETURN
 780 REM print move
 790
 800 REM --- PUSH ALL ----------------------------
 805 REM guarda a situacao de MOVE2 para futura utilizacao 
 810 LET a=lev   : GO SUB push a
 812 LET a=fonte : GO SUB push a
 814 LET a=aux   : GO SUB push a
 816 LET a=dest  : GO SUB push a
 820 RETURN
 830 REM push all
 840
 850 REM --- POP ALL ----------------------------
 855 REM restaura uma situacao anterior de MOVE2
 860 GO SUB pop a : LET dest =a
 862 GO SUB pop a : LET aux  =a
 864 GO SUB pop a : LET fonte=a
 866 GO SUB pop a : LET lev  =a
 870 RETURN
 880 REM pop all
 890 


---------------------------
ZE OLIVEIRA zarsoft(a)clix.pt
---------------------------