Pascal/Delphi O que eu entendi de recursividade

Leilson Frantchelino · 22 de agosto de 2019

Muita gente, inclusive eu, tem dificuldade em entender o que o programa faz nas iterações de recursividade. Vou mostrar abaixo o que eu entendi ao fazer Debugger do código de fatorial recursivo. Me corrijam se minha interpretação estiver errada, pois já quebrei a cabeça tentando entender a lógica. Esse foi o resultado mais lógico que cheguei "debugando" linha por linha.

Program FatRecursivo ;
Var n: integer;

Function Fat(n:integer): integer ;
  Begin
   if n = 0 then
     Fat:= 1;     
   else 
     Fat:= n * Fat(n-1)
  End;

Begin  
  write('Entre com o valor de n: ');
  readln(n);
  writeln('Valor de fat(n) => ', Fat(n));
  readkey;
End.

Empilha (iteração)                                             Desempilha (recursivamente)                                                                                           
Fat:= 5*Fat(4)  Chama a fuction novamente passando o 4         1:=1*Fat(1)=1
Fat:= 4*Fat(3)  Chama a fuction novamente passando o 3         1:=2*Fat(1)=2                                                                                                                                      
Fat:= 3*Fat(2)  Chama a fuction novamente passando o 2         2:=3*Fat(2)=6                                                                                                                 
Fat:= 2*Fat(1)  Chama a fuction novamente passando o 1         6:=4*Fat(6)=24                                                                                                                          
Fat:= 1*Fat(0) - if(n = 0) then Fat:=1                         24:=5*Fat(24)=120

Quando o programa principal chama a Function pela primeira vez, o Fat:= não recebe nada, pois ao chegar em Fat(n-1), a Function é chamada novamente, não permitindo que Fat:= receba o valor do cálculo de Fat:=n*Fat(n-1). Se calculasse, Fat:= iria receber 20, resultado de Fat:=5*Fat(4). Então, a iteração vai acontecendo até “n” ser 0, condição if n = 0.

Ao terminar a iteração (if n = 0 then Fat:=1), a Function vai fazer a ordem inversa, de baixo para cima. Agora sim Fat:= vai receber os valores do cálculo, pois a Function precisa retornar ao ponto da primeira chamada (Fat:= 5*Fat(4)). Fazendo a ordem inversa, o primeiro cálculo é (Fat:= 1*Fat(0)) que foi a última iteração. Devido ao comando if n = 0 then Fat:=1, o primeiro cálculo inicia-se assim 1:=1*Fat(1) = 1. Agora, uma após a outra, Fat:= recebe o valor do cálculo e, n é recuperado, mantendo o mesmo valor da iteração.

Obs: o programa Principal aguarda por um retorno da Function Fat que, por sua vez, se executa recursivamente para chegar a uma resposta. Em toda iteração (recursiva), de Function Fat, o valor do parâmetro n é diferente (resultado de (n-1)). Quando a chamada recursiva se encerra, o programa precisa voltar ao ponto em que a chamada ocorreu (de baixo para cima), recuperando os valores das variáveis locais.

Simon Viegas · 23 de agosto de 2019

Olá.

Em 22/08/2019 às 10:08, Leilson Frantchelino disse:

Quando o programa principal chama a Function pela primeira vez, o Fat:= não recebe nada, pois ao chegar em Fat(n-1), a Function é chamada novamente, não permitindo que Fat:= receba o valor do cálculo de Fat:=n*Fat(n-1). Se calculasse, Fat:= iria receber 20, resultado de Fat:=5*Fat(4). Então, a iteração vai acontecendo até “n” ser 0, condição if n = 0.

Acho que deveria excluir a parte do que "não faz". Não importa o que o programa não está fazendo, mas sim apenas o que faz. Outra coisa: no caso, como o programa saberia que daria 20 se ele não calculou o Fat(4)? De onde tirou que Fat(4) seria igual a 4? ou seja, não tem como saber o valor Fat(4) antes de executar o Fat(4), que por sua vez precisa esperar o Fat(3)... etc. Logo, não faz sentido essa suposição.

Sobre:

Em 22/08/2019 às 10:08, Leilson Frantchelino disse:

[...] pois a Function precisa retornar ao ponto da primeira chamada (Fat:= 5*Fat(4)).

Quem vai retornar ao ponto inicial não é a função, mas sim o programa (o computador)... que está com a execução de varias funções em cascata. Detalhe: uma execução de uma função recursiva nada mais é como se fosse uma execução de outra função qualquer... apenas existe o detalhe de ser ela mesma.

Seria algo como:

- O computador executa as instruções em uma ordem de prioridade. Ao invocar uma função, vai ter que fazer tudo que esta função tem para fazer e depois executará a próxima linha após essa função. Se dentro da função chamar outra função ou (procedimento), o computador também vai ter quer executar tudo que essa nova função tem que fazer, após volta para função anterior, e após voltar para estrutura inicial que invocou a primeira função... Ex.:

Function FuncaoB(n:integer): integer ;
  Begin
     FuncaoB := n * 23;
  End;

Function FuncaoA(n:integer): integer ;
  Begin
     FuncaoA := FuncaoB(n) * 4;
  End;

Function MinhaFuncao(n:integer): integer ;
  Begin
     MinhaFuncao := 10 * FuncaoA(n);
  End;

Entende? a função MinhaFuncao(), vai invocar outra função... que vai invocar outra, que vai invocar outra.. etc. É a mesma coisa (obs.: cada uma das funções pode ter ou não mais instruções dentro dela. Não importa!)... O ponto chave é que, ao invocar uma nova função qualquer (outra ou ela mesma), vai executar tudo que a nova função faz e retorna onde foi invocado. Apenas pode ocorrer que essa função invocar outras funções, logo seguindo a mesma lógica.

A diferença da recursividade é que você não precisa declarar várias funções "clones". Basta invocar a si mesmo... nesse caso, como está invocando si mesmo, precisa de uma estrutura qualquer para saber a hora de parar... (no caso a estrutura if/else, caso contrário ficaria invocando funções "infinitamente" - até acabar a memória).

Abaixo uma sequência de como interpreto o fluxo:

Fat(5) = 
Fat1 = 5 * Fat2(4) (empilha)
Fat2 = 4 * Fat3(3) (empilha)
Fat3 = 3 * Fat4(2) (empilha)
Fat4 = 2 * Fat5(1) (empilha)
Fat5 = 1 * Fat6(0) (empilha)
Fat6 = 1 (desempilha)
Fat5 = 1 * (1) (desempilha) //já que Fat6(0) retornou 1
Fat4 = 2 * (1) (desempilha) //já que Fat5(1) retornou 1
Fat3 = 3 * (2) (desempilha) //já que Fat4(2) retornou 2
Fat2 = 4 * (6) (desempilha) //já que Fat3(3 retornou 6
Fat1 = 5 * (24) (desempilha) //já que Fat2(4) retornou 24
Fat(5) = 120

obs.: os valores entre () são o valores que a função
  anterior retornou, ou seja: as funções funcionam, como
  uma variável especial, onde esta podem conter 
  instruções, mas que no final sempre retornam um valor nela 
  mesma. No caso da recursividade, cada vez que uma 
  nova instância é finalizada, a instância anterior
  vai receber o valor resultante dela.

Sobre:

Em 22/08/2019 às 10:08, Leilson Frantchelino disse:

Obs: o programa Principal aguarda por um retorno da Function Fat que, por sua vez, se executa recursivamente para chegar a uma resposta. Em toda iteração (recursiva), de Function Fat, o valor do parâmetro n é diferente (resultado de (n-1)). Quando a chamada recursiva se encerra, o programa precisa voltar ao ponto em que a chamada ocorreu (de baixo para cima), recuperando os valores das variáveis locais.

ATENÇÃO: ser diferente não tem relação com o "n-1"... mesmo se fosse um valor igual, cada função terá um n diferente (não pode confundir isso!). Como a variável foi passada por valor (em detrimento de passagem por referência, já que não tem o var), cada instância de função tem a sua própria variável local. (a variável local de cada função recebe o valor que foi dado no parâmetro, ou seja: é uma cópia do valor, e não uma referência)

Tente aí reformular a resposta.

Qualquer dúvida ou crítica é só postar.

No aguardo.

Leilson Frantchelino · 23 de agosto de 2019

Tudo bem Simon.

1 hora atrás, Simon Viegas disse:

De onde tirou que Fat(4) seria igual a 4? ou seja, não tem como saber o valor Fat(4) antes de executar o Fat(4), que por sua vez precisa esperar o Fat(3)... etc. Logo, não faz sentido essa suposição.

Aqui eu quis exemplificar de como seria o valor do parâmetro como se tivesse passado 5, assim Fat:= n * Fat(n-1), n recebe 5, então seria Fat:=5*Fat(4). Acabei esquecendo de por o 5 como exemplo. Desculpa.

1 hora atrás, Simon Viegas disse:

Quem vai retornar ao ponto inicial não é a função, mas sim o programa (o computador)... que está com a execução de varias funções em cascata. Detalhe: uma execução de uma função recursiva nada mais é como se fosse uma execução de outra função qualquer... apenas existe o detalhe de ser ela mesma.

Certinho Simon.

1 hora atrás, Simon Viegas disse:

ATENÇÃO: ser diferente não tem relação com o "n-1"... mesmo se fosse um valor igual, cada função terá um n diferente (não pode confundir isso!).

Sim, a cada iteração, terá a cópia de n com seu devido valor., n1, n2, n3...

Obrigado Simon. A intenção do post foi ajudar a quem tem dúvida e, como deixei escrito no post, gostaria de ajuda em consertar erros. Você foi um que contribui com isto.

Fiz uma pequena mudança no código. A cada iteração, trás o valor.

Program FatRecursivo ;
Var n, i: integer;

Function Fat(n:integer): integer ;
  Begin
   if n = 0 then
     Fat:= 1     
   else 
     Fat:= n * Fat(n-1)
  End;

Begin  
  write('Entre com o valor de n: ');
  readln(n);
 for i:=1 to n do
  begin
    writeln('Fatorial de ',i,'! = ' , Fat(i) );  
  //readkey;
  end;
End.

adicionado 9 minutos depois

1 hora atrás, Simon Viegas disse:

No caso da recursividade, cada vez que uma nova instância é finalizada, a instância anterior vai receber o valor resultante dela.

Esqueci de comentar essa parte. Simon, é realmente isso, no seu exemplo, você demonstrou isso. Foi o que tentei expor também aqui:

Desempilha (recursivamente) 
1:=1*Fat(1)=1 
1:=2*Fat(1)=2 
2:=3*Fat(2)=6 
6:=4*Fat(6)=24 
24:=5*Fat(24)=120

Simon Viegas · 24 de agosto de 2019

Só um adendo:

Ao usar:

Em 23/08/2019 às 15:48, Leilson Frantchelino disse:
writeln('Fatorial de ',i,'! = ' , Fat(i) );

Leem-se, por exemplo: "Fatorial de 5 fatorial". O que não corresponde ao resultado. Logo, poderia usar:

writeln('Fatorial de ', i, ' = ', Fat(i));

ou

writeln(i, '! = ', Fat(i));

Leilson Frantchelino · 26 de agosto de 2019

Opa, valeu Simon, mais uma contribuição. Alterado.

Program FatRecursivo ;
Var n, i: integer;

Function Fat(n:integer): integer ;
  Begin
   if n = 0 then
     Fat:= 1     
   else 
     Fat:= n * Fat(n-1)
  End;

Begin  
  write('Entre com o valor de n: ');
  readln(n);
 for i:=1 to n do
  begin
    writeln('Fatorial de ',i,' = ' , Fat(i) );  
  //readkey;
  end;
End.