BASIC APASCALADO III - A iteração ataca novamente!

Não se surpreendam por ver aqui  outra vez a função  factorial; ela é fatal  como o destino
 em linguagens imperativas (BASIC,PASCAL,etc.).

Se pensaram no exercício  proposto no ultimo artigo desta série, devem ter chegado à conclusão 
que, às vezes, é muito mais eficiente resolver os problemas iterativamente (num ciclo repetitivo) 
do que recorrer à recursividade.

Por isso  é que  muitas vezes  se luta para eliminar a recursividade. E, o  primeiro passo
 para isso é eliminar a necessidade de stack. A solucao é passar directamente 
 as variáveis  modificadas, recorrendo a uma função auxiliar:

(recursividade normal)
	FACT(n) = | n=0  ->  1
                  | n>0  ->  n*FACT(n-1)

(recursividade directa)
	FACT(i) = FACT2(i,1)

	FACT2(n,f) = | n=0  ->  f
                     | n>0  ->  FACT2(n-1,f*n)

Legenda:
	"*"   - operação principal
	"1"   - elemento neutro da operação principal
	"n-1" - decremento

Exemplo de execução da recursividade normal:
FACT(3) = 3*FACT(2) = 3*2*FACT(1) = 3*2*1*FACT(0) = 3*2*1*1 = 6

Exemplo de execução da recursividade directa:
FACT(3) = FACT2(3,1) = FACT2(2,1*3) = FACT2(1,1*3*2) = FACT2(0,1*3*2*1) = 1*3*2*1 = 6

Isto é facilmente  transformável  num ciclo iterativo:

Algoritmo iterativo:

	LER(n)
	f <-- 1
	ENQUANTO n>0 FAZER 
		| f  <--  n*f
		| n  <--  n-1

Exemplo de execução com um ciclo iterativo:
n <-- 3 ; f <-- 1
          f <-- 3*1 = 3 ; n <-- 3-1 = 2
          f <-- 2*3 = 6 ; n <-- 2-1 = 1
          f <-- 6*1 = 6 ; n <-- 1-1 = 0

Moral da historia: Abaixo a recursividade.

EXERCICIO: Torres de Hanoi
	Regras:
	1 - Existem 3 pilhas.
	2 - A primeira pilha tem discos de diferentes tamanhos.
	3 - O objectivo  é  mover  os discos  para a terceira pilha.
	4 - Só se pode mover um disco de cada vez.
	5 - Nunca pode estar  um disco maior  em cima de um mais pequeno.

Agora resolvam isto iterativamente... se tiverem coragem.

No próximo artigo discutiremos este problema.


NOTA: Para não abusar do espaço do MICROSE7E, estes artigos têm apenas as explicações fundamentais. 
Aconselho-vos  a testar  todos  os programas aqui apresentados.

No caso  de ficarem com dúvidas  sobre o seu funcionamento, corram o programa com papel e lápis,
 observando as variáveis durante a execução.

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

PROGRAM factorial (INPUT,OUTPUT);

VAR
  arg :INTEGER;
  f   :REAL;

  PROCEDURE escrever_resultado (res:REAL); {-----} 
  BEGIN
    WRITELN('FACT(arg) = ',res);
  END; {--- escrever_resultado ---}

  FUNCTION fact2 (n,f:INTEGER):INTEGER; {----------} 
  VAR res :INTEGER;
  BEGIN
    IF n=0 THEN res:=f
	   ELSE res:=fact2(n-1,f*n);
    fact2:=res
  END; {--- fact2 ---}

  FUNCTION fact (i:INTEGER):INTEGER; {-------------} 
  BEGIN
    fact:=fact2(i,1)
  END; {--- fact ---}

  PROCEDURE ler_argumento (VAR argumento:INTEGER); 
  BEGIN
    WRITE('diz um numero [0..33]  '); 
    READLN(argumento)
  END; {--- ler_argumento ---}

BEGIN {--- main_prog ----------------------------} 
  ler_argumento(arg);
  f := fact(arg);
  escrever_resultado(f)
END. {--- main_prog -----------------------------}


   5
  10 REM PROGRAM factorial (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 = 500
 115 LET ler arg = 600 
 120 LET fact = 700 
 125 LET fact2 = 800 
 130 LET escrever res = 900
 190
 200 REM --- VARIAVEIS PRINCIPAIS ---------------
 210 REM arg  argumento de factorial
 215 REM a    argumento auxiliar e dado para stack 
 220 REM fact resultado
 225 REM f    resultado auxiliar
 290
 500 REM --- MAIN PROG --------------------------
 510 GO SUB ler arg
 520 GO SUB fact
 530 GO SUB escrever res
 540 STOP
 580 REM main prog
 590
 600 REM --- LER ARG ----------------------------
 610 PRINT "argumento [0..33] = ";
 620 INPUT arg : PRINT arg
 630 RETURN
 680 REM ler arg
 690
 700 REM --- FACT -------------------------------
 710 LET f=1    : REM neutro da operacao principal 
 720 LET a=arg  : REM argumento
 730 GO SUB fact2
 740 LET fact=f
 750 RETURN
 780 REM fact
 790
 800 REM --- FACT2 ------------------------------
 810 IF a <  1 THEN REM resultado = f
 820 IF a >= 1 THEN LET f=f*a : LET a=a-1 : GO SUB fact2
 830 RETURN
 880 REM fact2
 890
 900 REM --- ESCREVER RES -----------------------
 910 PRINT "FACT(";arg;") = ";fact
 920 RETURN
 980 REM escrever res
 990

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