RECURSIVIDADE


  Após trabalhar com sub-rotinas, você já deve ter se perguntado: posso chamar uma procedure ou função de dentro dela mesmo? A resposta é sim. A esse tipo de invocação de sub-rotina para ela mesmo é chamado de recursividade.

  Exemplo:
var i : integer;

procedure loop;
begin
  loop;
end;

begin
  loop;
end.
  Observe que esse procedimento é infinito, conforme ilustra o código anterior. Uma vez posto em execução, a recursividade ficará executando infinitamente (até estourar a pilha).
  O problema em questão é sinalizar para que esse procedimento pare em um dederminado instante, sob alguma condição.
  O código a seguir impõe uma condição para que a recursividade pare, quando i atingir o valor igual a 10. Para isso, é necessário que a sub-rotina modifique o valor de i e que a condição de parada seja obrigatoriamente atingida.
var i : integer;

procedure loop;
begin
  if (i<10) then
  begin
    i := i + 1;
    loop;
  end;
end;

begin
  i:=1;
  loop;
end.
  Cada vez que o procedimento loop é chamado no exemplo anterior, a variável global é incrementada (aumentada) de 1 unidade. Assim, logo chegará ao valor 10.
  Por outro lado, a cada chamada recursiva, os valores das variáveis locais são empilhados em memória e uma nova chamada ao procedimento é feita. Em outras palavras, quando uma nova chamada recursiva é feita, novos valores para as variáveis locais são estabelecidos. Obviamente, isso não acontece para as variáveis globais, porque essas possuem escopo global.
  Assim, caso fosse utilizada uma variável local no procedimento loop, o valor seria sempre reinicializado e nunca atingiria o valor igual a 10.

Exemplo de ERRO ao utilizar uma variável local como critério de parada:
procedure loop;
var i : integer;
begin
  i := 1;

  if (x<10) then
  begin
    i := i + 1;
    loop;
  end;
end;

begin
  loop;
end.
  Vamos modificar o programa correto, de forma a informar o valor de i.
var i : integer;

procedure loop;
begin
  if (i<10) then
  begin
    i := i + 1;
    write(' ', i);
    loop;
  end;
end;

begin
  i:=1;
  loop;
end.
Saída:
2 3 4 5 6 7 8 9 10

  Agora, vamos inverter as linhas do write e loop e ver o que acontece:
var i : integer;

procedure loop;
begin
  if (i<10) then
  begin
    i := i + 1;
    loop;
    write(' ', i);
  end;
end;

begin
  i:=1;
  loop;
end.
Saída:
10 10 10 10 10 10 10 10 10

  Como assim? Escreveu tudo 10?
  Na verdade, quando uma sub-rotina chama outra sub-rotina (ou ela mesmo), a execução da sub-rotina pára exatamente na linha onde essa chamada é feita. Então, a sub-rotina chamada entra em execução. Ao terminar a execução da sub-rotina chamada, a primeira sub-rotina continua a executar, a partir da linha seguinte daquela chamada. Para entender melhor isso, veja o exemplo abaixo:
procedure proc2;
begin
  writeln('linha 3');
  writeln('linha 4');
end;

procedure proc1;
begin
  writeln('linha 1');
  proc2;
  writeln('linha 2');
end;

begin
  proc1;
end.
Saída:
linha 1
linha 3
linha 4
linha 2

  Observe que em proc1 foi feita uma chamada para proc2. Proc1 executou até esse linha, imprimindo a mensagem "linha1". Então, proc2 entrou em execução e imprimiu as mensagens "linha 3" e "linha 4". Ao terminar a execução de proc2, o programa voltou para proc1 e continuou a executar na linha seguinte da chamada de proc1, imprimindo a mensagem "linha 2".
  O mesmo aconteceu no exemplo da recursividade que imprimiu tudo 10. Chamadas sucessivas ao loop são feitas, e isso só para quando uma dada condição é satisfeita, no caso i atingir o valor 10 (ou maior). Quando i=10, nenhuma nova chamada é feita e o retorno em cascata é realizado.
  Como i é uma variável global, todas os procedimentos empilhados irão imprimir o mesmo valor.

  Para demonstrar o efeito de pilha em chamadas recursivas, vamos armazenar o valor de i em uma variável local chamada x:
var i : integer;

procedure loop;
var x : integer;
begin
  if (i<10) then
  begin
    i := i + 1;
    x := i;
    loop;
    write(' ', x);
  end;
end;

begin
  i:=1;
  loop;
end.
Saída:
10 9 8 7 6 5 4 3 2

Roda código em verde - Sentido das chamadas >>>>>>
if (i<10) then begin
  i := i + 1;
  x := i; { x=2 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=3 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=4 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=5 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=6 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=7 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=8 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=9 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i; { x=10 }
  loop;
  write(' ', x);
end;
if (i<10) then begin
  i := i + 1;
  x := i;
  loop;
  write(' ', x);
end;
<<<<<< Sentido do desempilhamento - Roda código em azul.
  Obs: O trecho de código em vermelho não é executado, pois o valor máximo de i foi atingido.

  Agora, vamos criar uma função que calcula o fatorial de um número, utilizando a recursividade.
function fatorial(n : integer):integer;
begin
  if n <= 1 then
    fatorial:=1;
  else
    fatorial:=n*fatorial(n-1); 
end;

begin
  writeln(fatorial(4));
end. 
A saída é 24.

  Agora vamos entender as interações da função fatorial:
  1. Recebe valor 4.
  2. Passo 1:  fatorial := 4*fatorial(3);
  3. Fatorial é chamada de dentro com o valor 3.
  4. Passo 2: fatorial := 3*fatorial(2);
  5. Passo 3: fatorial := 2*fatorial(1);
  6. Se valor for menor ou igual a 1, retorna 1. Fim das chamadas sucessivas.
  7. Vamos desempilhar.
  8. Passo 3: fatorial := 2*1;
  9. Passo 2: fatorial := 3*2;
  10. Passo 1: fatorial := 4*6;
  11. Retorna o valor 24 para a chamada do corpo principal do programa.


/MARMSX/CURSOS/PASCAL