Curso de Basic
Pilhas e Recursividade
Você está em: MarMSX >> Cursos >> BASIC
Pilhas
Às vezes, necessitamos armazenar na memória alguns valores que mais tarde serão necessários. O mecanismo de pilha permite armazenar valores na memória do mesmo modo que uma pilha de livros, onde o último livro a entrar na pilha é o primeiro a sair - LIFO (Last In, First Out).
A pilha contém um vetor com valores "empilhados" e um ponteiro para o topo da pilha (TOP). Duas são as operações permitidas na pilha: PUSH, onde inserimos no topo da pilha um novo valor e POP, onde retiramos da pilha o valor do topo.
Em Basic, podemos utilizar um vetor para armazenar os dados da pilha. Veja o exemplo a seguir.
10 DIM PILHA(10)
20 TP=0 ' Topo da pilha = vazia
30 TP=TP+1 : PILHA(TP)=15 ' Push 15
40 TP=TP+1 : PILHA(TP)=78 ' Push 78
200 '
205 ' Imprime pilha
210 '
220 CLS:LOCATE 0,0:PRINT"Pilha:"
230 FOR F=TP TO 1 STEP -1
240 LOCATE 0,(TP+2)-F:PRINT PILHA(F);
250 IF F=TP THEN PRINT TAB(4);"<-top";
260 NEXT F
Saída:
Pilha:
78 <-top
15
Nesse exemplo criamos uma pilha com tamanho igual a 10. O primeiro valor empilhado foi 15 e o segundo foi 78. Assim, 78 está no topo da pilha e é o próximo elemento a ser removido, caso se deseje remover um item da pilha. Veja o próximo exemplo.
10 DIM PILHA(10)
20 TP=0 ' Topo da pilha = vazia
30 TP=TP+1 : PILHA(TP)=15 ' Push 15
40 TP=TP+1 : PILHA(TP)=78 ' Push 78
50 GOSUB 200
60 PRINT"Tecle algo ...":A$=INPUT$(1)
70 V=PILHA(TP) : TP= TP-1 ' Pop
80 GOSUB 200
90 END
200 '
205 ' Imprime pilha
210 '
220 CLS:LOCATE 0,0:PRINT"Pilha:"
230 FOR F=TP TO 1 STEP -1
240 LOCATE 0,(TP+2)-F:PRINT PILHA(F);
250 IF F=TP THEN PRINT TAB(4);"<-top";
260 NEXT F
270 RETURN
Saída:
Pilha:
78 <-top
15
Tecle algo ...
Pilha:
15 <-top
Na linha 70, retiramos o valor 78 do topo da pilha e o colocamos na variável V.
Assim, devemos realizar em cada operação:
- PUSH - colocar o valor na pilha e incrementar o ponteiro de topo (TOPO = TOPO + 1).
- POP - remover o valor da pilha e decrementar o ponteiro de topo (TOPO = TOPO - 1).
Soluções Iterativas e Recursivas
Há problemas em que a solução é de forma iterativa, ou seja, devemos repetir os mesmos passos N vezes até que uma dada condição seja atendida. O exemplo clássico é o cálculo fatorial, onde devemos multiplicar um número N pelos seus antecessores até chegar a 1 (de N-1 a 1).
Por exemplo, 4! é:
4! = 4 X 3 X 2 X 1
Em termos computacionais, teríamos:
N ← 4;
F ← 1;
para i= N até 1 faça
F ← F * i;
fim_para;
Iteratividade (loop)
A iteratividade é a repetição dos mesmos passos, necessários para resolver um problema. o mecanismo utilizado para isso é o laço ou loop.
Podemos resolver o problema da fatoração através de um loop simples, onde variamos "i" de N até 2, pois a multiplicação por 1 é desnecessária.
10 INPUT"Qual o fator N";N
20 IF N<0 OR N>10 THEN 10
30 F=1 : IF N<2 THEN 70
40 FOR I=2 TO N
50 F=F*I
60 NEXT I
70 PRINT"O fatorial e':";F
No caso de N ser 0 ou 1, não há necessidade de cálculos porque são 1 por definição. Valores de N maiores que 10 são descartados, porque os valores para eles são muito grandes.
Recursividade
A recursividade é quando uma função chama ela mesma. Esse mecanismo pode ser utilizado para a solução de diversos problemas, inclusive os iterativos.
Veja o exemplo a seguir
10 GOSUB 100
20 END
100 ' Funcao recursiva
110 PRINT "Isso e' repetitivo"
120 GOTO 100 ' Chama ela mesma
Assim como na iteratividade, devemos impor uma condição de parada para a recursividade. Caso contrário, como visto no exemplo acima, o processo nunca irá parar.
Podemos resolver o problema da fatoração através da recursividade. Veja o exemplo a seguir.
10 INPUT"Qual o fator N";N
20 IF N<0 OR N>10 THEN 10
30 F=1 : IF N<2 THEN 70
40 GOSUB 200
70 PRINT"O fatorial e':";F
80 END
200 ' Funcao fatorial
210 IF N=1 THEN RETURN
220 F=F*N
230 N=N-1
240 GOTO 210
Podemos chamar a função através do GOSUB. Entretanto, devemos "queimar" cada GOSUB dado com o um RETURN. Assim, temos:
240 GOSUB 210
250 RETURN
Onde o RETURN da linha 250 será o retorno correspondente a cada chamada GOSUB da linha 240.
Ao utilizarmos o comando TRON, temos a seguinte ordem de linhas executadas para N=3:
10, 20, 30, 40,
200, 210, 220, 230, 240, ' N=3
210, 220, 230, 240, ' N=2
210, ' N=1
250, 250, ' Retornos
70, 80
Recursividade por meio de pilhas
Há determinados tipos de problemas em que é necessário armazenar os valores das variáveis entre uma chamada e outra da recursividade. É o caso do flood-fill ou enchente, que tem como finalidade preencher pontos na tela com uma nova cor, em áreas somente onde o valor de cor é o valor especificado. Entretanto, ele somente agrega pontos vizinhos ao ponto de partida.
Utilizaremos a seguinte matriz 7x7 nos exemplos de flood-fill.
111
11111
1111111
1111111
1111111
11111
111
Quais são os passos necessários para criar uma função recursiva que preenche a bola usando o flood-fill? Vejamos no pseudo-código a seguir.
mapa vetor(7,7);
funcao fill(x, y : inteiro; cor, nova cor : caractere)
// Retorna se coordenada fora do mapa
se coordenadas_fora_do_mapa(x,y) então retorna;
// Retorna se cor atual for diferente da especificada
se mapa(x,y) ≠ cor então retorna;
// Altera cor
mapa(x,y) ← novacor;
// Chamadas recursivas aos pontos vizinhos
fill(x+1, y, cor, novacor);
fill(x-1, y, cor, novacor);
fill(x, y+1, cor, novacor);
fill(x, y-1, cor, novacor);
fim_funcao;
Em linguagens como o Pascal e C, quando realizamos as chamadas recursivas, o próprio sistema se encarrega de salvar o contexto das variáveis (valores). Assim, esses valores não são perdidos quando uma nova chamada é feita à função. Veja o exemplo a seguir.
#include <stdio.h>
char mapa[7][7] = {' ',' ','1','1','1',' ',' ',
' ','1','1','1','1','1',' ',
'1','1','1','1','1','1','1',
'1','1','1','1','1','1','1',
'1','1','1','1','1','1','1',
' ','1','1','1','1','1',' ',
' ',' ','1','1','1',' ',' '};
void fill(int x, int y, char cor, char novacor)
{
if ((x<0) || (x>6) || (y<0) || (y>6))
return;
if (mapa[x][y] != cor)
return;
mapa[x][y] = novacor;
// Espalha por vizinhos
fill(x+1, y, cor, novacor);
fill(x-1, y, cor, novacor);
fill(x, y+1, cor, novacor);
fill(x, y-1, cor, novacor);
}
void imprime()
{
int x,y;
for (y=0; y<7; y++)
{
for (x=0; x<7; x++)
printf("%c",mapa[x][y]);
printf("\n");
}
}
main()
{
imprime();
fill(4,4,'1','4');
imprime();
}
Em Basic, não conseguiríamos realizar as quatro chamadas recursivas sem perder os valores de X e Y. Dessa forma, utilizaremos uma pilha para armazenar as coordenadas X e Y entre as chamadas.
A função recursiva então terá o trabalho de ir desempilhando coordenadas X e Y e realizando as alterações. O controle da pilha será externo à função fill.
Não podemos cair na tentação de colocar um GOTO ou GOSUB em cada chamada recursiva do flood-fill, pois isso acabaria acarretando na perda das coordenadas X,Y originais para as próximas linhas de chamadas. Assim, vamos empilhar todas de uma vez!
A nossa primeira tarefa é colocar na pilha o ponto de partida 4,4 e disparar a função fill.
Vejamos a solução em Basic.
05 SCREEN 0 : WIDTH 40
10 DIM MAPA$(8,7):DIM PILHA(100,2):TP=0
20 FOR Y=1 TO 7:FOR X=1 TO 7
30 READ A : MAPA$(X,Y)=CHR$(A)
40 NEXT X,Y
50 GOSUB 500
55 PRINT:PRINT"Tecle algo ...":A$=INPUT$(1)
60 ' Estabelece ponto de partida, a cor e nova_cor
70 TP=1 : PILHA(TP,1)=4 : PILHA(TP,2)=4 ' Push X,Y
80 CO$="1":NC$="4"
90 ' Loop de controle
100 GOSUB 200
110 IF TP<>0 THEN 100
120 GOSUB 500
130 END
200 ' Funcao fill
210 X=PILHA(TP,1):Y=PILHA(TP,2):TP=TP-1 ' Pop
220 IF X<1 OR X>7 OR Y<1 OR Y>7 THEN RETURN
230 IF MAPA$(X,Y) <> CO$ THEN RETURN
240 MAPA$(X,Y)=NC$
250 TP=TP+1 : PILHA(TP,1)=X+1 : PILHA(TP,2)=Y ' Push X+1,Y
260 TP=TP+1 : PILHA(TP,1)=X-1 : PILHA(TP,2)=Y ' Push X-1,Y
270 TP=TP+1 : PILHA(TP,1)=X : PILHA(TP,2)=Y+1 ' Push X,Y+1
280 TP=TP+1 : PILHA(TP,1)=X : PILHA(TP,2)=Y-1 ' Push X,Y-1
290 RETURN
500 ' Imprime mapa
510 FOR Y=1 TO 7:FOR X=1 TO 7
520 LOCATE X,Y:PRINT MAPA$(X,Y);
530 NEXT X,Y
540 RETURN
600 ' Dados mapa
610 DATA 32,32,49,49,49,32,32
620 DATA 32,49,49,49,49,49,32
630 DATA 49,49,49,49,49,49,49
640 DATA 49,49,49,49,49,49,49
650 DATA 49,49,49,49,49,49,49
660 DATA 32,49,49,49,49,49,32
670 DATA 32,32,49,49,49,32,32
Um loop fora da função fill (linhas 100-110) controla se a pilha acabou. Se não, chame a função até acabar a pilha.