BASIC APASCALADO II - Recursividade ?!  Que bicho é esse ?

Para  quem  não  sabe,  a característica  da recursividade é a definição de 
uma coisa a partir dela própria.

Por exemplo, com a função factorial:
	n! = n*(n-1)!     FACT(n) = n*FACT(n-1)

	Se isto não parar em algum sítio,  não serve para nada; por isso, deve-se acrescentar 0! = 1.

Já experimentei meter isto  no Spectrum sob a forma DEF FN, por exemplo:
	DEF FN f(n) = (n=0)*1 + (n>0)*(n*FN f(n-1)), 
     ou DEF FN f(n) = (1 AND (n<=1)) + ((n*FN f(n-1)) AND (n>1)),
mas, isto não funciona devido ao facto  da segunda parte  da definição ser sempre executada  e 
acabar por rebentar a memória.

Pensando bem,  a recursividade  não é coisa que se faça em BASIC.

No entanto, como viram, a recursividade está associada a uma simplicidade atraente. 
O que é um motivo suficiente para a estudar.

Segue-se    um    programa    em    PASCAL, e a sua versao em BASIC apascalado,  para resolver
a funcao factorial recursivamente.  E' apresentada uma  stack (pilha de dados)  de comprimento 
fixo e em seguida uma stack optimizada.

No próximo artigo veremos como implementar a recursividade sem recorrer a stacks.

Exercício: Programar a seguinte função de fibonnaci recursivamente:
	FIB(1) = 1
	FIB(2) = 1
	FIB(n) = FIB(n-2) + FIB(n-1) 

{---------==========----------==========---------} 

PROGRAM factorial (INPUT,OUTPUT);
VAR
  arg  :INTEGER;
  f    :REAL;

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

FUNCTION fact (arg:INTEGER):REAL; {------------} 
VAR res :REAL;
BEGIN
  IF arg < 1 THEN res:=1
             ELSE res:=arg*fact(arg-1); 
  fact:=res
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 -----------------------------}


--------------- maximo de colunas = 50 -----------
   5
  10 REM PROGRAM factorial (Keyboard,Screen)
  20 REM (C) 1987 ZARSOFT
  30 REM Written by ZE OLIVEIRA
  40 REM BASIC apascalado / BASIC Sinclair
  50
 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 
 150 LET init stack = 1000
 155 LET push a = 1100
 160 LET pop a = 1200
 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 GO SUB init stack
 720 LET a=arg
 730 GO SUB fact2
 740 LET fact=f 750 RETURN
 780 REM fact
 790
 800 REM --- FACT2 -------------------------------
 810 IF a <  2 THEN LET f=1
 820 IF a >= 2 THEN GO SUB push a : LET a=a-1 :
: GO SUB fact2 : GO SUB POP a : LET f=a*f
 830 RETURN
 880 REM fact2
 890
 900 REM --- ESCREVER RES ------------------------
 910 PRINT "FACT(";arg;") = ";fact
 920 RETURN
 980 REM escrever res
 990
1000 REM --- INIT STACK -------------------------
1010 REM stack de reais - comprimento fixo
1030 REM VARIAVEIS: -----------------------------
1032 REM a	variavel argumento da stack
1034 REM s	array de dados
1036 REM pointer	apontador para o topo da stack
1038 REM
1050 DIM s(40) : REM maximo = 40
1060 LET pointer=0
1070 RETURN
1080 REM init stack
1090
1100 REM --- PUSH A -----------------------------
1110 LET pointer=pointer+1
1120 LET s(pointer)=a
1130 RETURN
1180 REM push a
1190
1200 REM --- POP A ------------------------------
1210 LET a=s(pointer)
1220 LET pointer=pointer-1
1230 RETURN
1280 REM pop a
1290 -------------------------------------------------
1000 REM --- INIT STACK -------------optimizada--
1010 REM stack de inteiros - comprimento variavel 
1012 REM funciona com inteiros de 2 bytes
1014 REM adaptavel para outro numero de bytes
1016 REM neste programa so' era necessario 1 byte 
1030 REM VARIAVEIS: -----------------------------
1032 REM a	variavel argumento da stack
1033 REM s$	array de dados
1034 REM l	comprimento da stack
1035 REM high,low  argumento na base 256 1038 REM
1050 LET s$=""
1070 RETURN
1080 REM init stack
1090
1100 REM --- PUSH A -----------------------------
1110 LET high=INT(a/256)
1120 LET low=a-256*high
1130 LET s$=s$+CHR$(low)+CHR$(high)
1140 RETURN
1180 REM push a
1190
1200 REM --- POP A ------------------------------
1210 LET l=LEN s$
1220 LET a=CODE(s$(l-1))+256*CODE(s$(l))
1230 LET s$=s$(1 TO l-2)
1270 RETURN
1280 REM pop a
1290 
-----------------------------
ZE OLIVEIRA zarsoft(a)clix.pt
-----------------------------