Portugol Dificuldade Algoritmo com Função Recursiva (Portugol)

Primon · 29 de maio de 2019

Olá pessoal do Clube do Hardware, estou cursando ADS através do EAD e estou na disciplina (Algoritmo e lógica de programação), resolvi me inscrever no fórum para tirar algumas dúvidas e com isso progredir nessa matéria e também ajudar no que estiver ao meu alcance, eu estou com dificuldade em resolver um exercício que contém função recursiva, "só para deixar claro eu não quero apenas usufruir do conhecimentos de terceiros para garantir nota, e sim conseguir entender o problema e consequentemente aprender o conteúdo". estive procurando vários vídeos sobre funções recursiva eles dão sempre os exemplos clássicos como Fatorial e Fibonacci, eu até consegui compreender um pouco a lógica nesses exemplos. Porém quando vou resolver a questão que citei anteriormente eu não consigo desenvolver. Detalhe estou aprendendo o Portugol, a questão é a seguinte:

Assim, considere o seguinte trecho de pseudocódigo a seguir:

01 - Algoritmo processaVetor
02 -     Funcao SVR (v: vetor [1..3] de inteiro, n: inteiro) : inteiro
03 -         Início
04 -             Se (n = 1) então
05 -                 retorne v [n]
06 -             Senão
07 -                 retorne v [n] + SVR (v, n-1)
08 -             Fim_se
09 -         Fim_funcao
10 - Var A: vetor [1..3] de inteiro 
11 -         s: inteiro
12 - InÍcio
13 -     A [1] <- 30
14 -     A [2] <- 20
15 -     A [3] <- 10
16 -     s <- SVR (A, 3)
17 -     ESCREVA (s)
18 - Fim.

Ao realizar o teste de mesa no algoritmo recém apresentado, constata-se que seria apresentada a seguinte mensagem na tela do computador.

E ai vem as alternativas.

OBS: Caso queriam alterar os valores das variáveis, a fim de explicar sem precisar resolver a questão esta perfeito, eu só preciso compreender o problema.

Simon Viegas · 29 de maio de 2019

Olá @Primon. Seja bem-vindo ao Fórum do Clube do Hardware.

Recursividade ocorre quando dentro um método é invocado outro método, mas sendo que esse outro método é ele próprio. Como assim?

Imagine que dentro da função SVR() você precise utilizar a função SOMAR(). Logo, dentro da função SVR() estará invocando uma outra função, que seria a SOMAR(). Nada de mais, né? A função SOMAR() vai fazer o que tem que fazer e retornar um valor em si mesma. Se lá dentro de SOMAR() estiver invocando um função qualquer, a função qualquer vai fazer o que tem que fazer e retornar o valor para SOMAR()... que vai utilizar e no final a função que invocou somar vai ter o resultado... por vai vai. Daí, apenas ocorre a SVR() está invocando a própria função SRV(), ou seja, ela mesma. A segunda SRV() vai fazer o que tem que fazer e retornar a primeira... se na segundo invocar a terceira, a terceira vai fazer o que tem que fazer, retornar para segunda, que por sua vez a segunda retorna para primeira...

Como perceberá, as funções recursivas devem está preparadas (para serem recursivas), pois caso contrário, uma função iria invocar uma nova, que por sua vez a nova invocaria uma outra nova, esta última invocaria mais uma nova etc etc. (até esgotar os recursos e travar). Observe que no exemplo do seu código, é invocado uma nova com parâmetros diferentes... vai chegar um momento que a última vai parar e começará a voltar...

Tentar entender o fluxo, imagine que um método (no caso uma "função") seja um programa independente. No caso, cada vez que você invocar esse método, seria equivalente a abrir uma cópia de um programa. O grande ponto chave é abstrair que cada variável que essa cópia do "programa" utilizará será independente das outras variáveis do programa principal e também independente das variáveis das outras cópias desse programa.

Vamos pro exemplo:

s <- SVR (A, 3)

Primeiro vai fazer o que está a direita do s. Vai invocar o SRV()... criaria uma cópia do "programa". Vamos imaginar com algo assim: SVR1([30,20,10], 3).

O fluxo continua normalmente. Vai executar as instruções em SVR1(). Como n é igual a 3, que não é igual a 1, vai pro senão. Lá tem:

retorne v [n] + SVR (v, n-1)

Aqui mesma coisa. Primeiro vai fazer o que está a direita do retorne. Como tem uma função, vai invocar ela. O computador vai criar uma cópia dessa função (que "por acaso" é a mesma função que está no momento). Vamos imaginar que ficaria: SVR2([30,20,10], 2). Nele, vai seguir o fluxo também e por aí vai.

Perceba que quando n tiver igual a 1, vai seguir por outro caminho. Lá em SVR3([30,20,10], 1) vai retornar simplesmente 30, ou seja, em SVR2([30,20,10], 2), onde o SVR3([30,20,10], 1) foi invocado, vai receber 30. Que será "concatenado" a direita de v[n], que em SVR2([30,20,10], 2) vale 20, logo, ficaria 2030... que será o que será retornado para função anterior SVR1([30,20,10], 3)... por ai vai.

Tente ver se compreendeu... qualquer dúvida é só perguntar.

Primon · 30 de maio de 2019

9 horas atrás, Simon Viegas disse:
Olá @Primon. Seja bem-vindo ao Fórum do Clube do Hardware.

Recursividade ocorre quando dentro um método é invocado outro método, mas sendo que esse outro método é ele próprio. Como assim?

Imagine que dentro da função SVR() você precise utilizar a função SOMAR(). Logo, dentro da função SVR() estará invocando uma outra função, que seria a SOMAR(). Nada de mais, né? A função SOMAR() vai fazer o que tem que fazer e retornar um valor em si mesma. Se lá dentro de SOMAR() estiver invocando um função qualquer, a função qualquer vai fazer o que tem que fazer e retornar o valor para SOMAR()... que vai utilizar e no final a função que invocou somar vai ter o resultado... por vai vai. Daí, apenas ocorre a SVR() está invocando a própria função SRV(), ou seja, ela mesma. A segunda SRV() vai fazer o que tem que fazer e retornar a primeira... se na segundo invocar a terceira, a terceira vai fazer o que tem que fazer, retornar para segunda, que por sua vez a segunda retorna para primeira...

Como perceberá, as funções recursivas devem está preparadas (para serem recursivas), pois caso contrário, uma função iria invocar uma nova, que por sua vez a nova invocaria uma outra nova, esta última invocaria mais uma nova etc etc. (até esgotar os recursos e travar). Observe que no exemplo do seu código, é invocado uma nova com parâmetros diferentes... vai chegar um momento que a última vai parar e começará a voltar...

Tentar entender o fluxo, imagine que um método (no caso uma "função") seja um programa independente. No caso, cada vez que você invocar esse método, seria equivalente a abrir uma cópia de um programa. O grande ponto chave é abstrair que cada variável que essa cópia do "programa" utilizará será independente das outras variáveis do programa principal e também independente das variáveis das outras cópias desse programa.

Vamos pro exemplo:
s <- SVR (A, 3)
Primeiro vai fazer o que está a direita do s. Vai invocar o SRV()... criaria uma cópia do "programa". Vamos imaginar com algo assim: SVR1([30,20,10], 3).

O fluxo continua normalmente. Vai executar as instruções em SVR1(). Como n é igual a 3, que não é igual a 1, vai pro senão. Lá tem:
retorne v [n] + SVR (v, n-1)
Aqui mesma coisa. Primeiro vai fazer o que está a direita do retorne. Como tem uma função, vai invocar ela. O computador vai criar uma cópia dessa função (que "por acaso" é a mesma função que está no momento). Vamos imaginar que ficaria: SVR2([30,20,10], 2). Nele, vai seguir o fluxo também e por aí vai.

Perceba que quando n tiver igual a 1, vai seguir por outro caminho. Lá em SVR3([30,20,10], 1) vai retornar simplesmente 30, ou seja, em SVR2([30,20,10], 2), onde o SVR3([30,20,10], 1) foi invocado, vai receber 30. Que será "concatenado" a direita de v[n], que em SVR2([30,20,10], 2) vale 20, logo, ficaria 2030... que será o que será retornado para função anterior SVR1([30,20,10], 3)... por ai vai.

Tente ver se compreendeu... qualquer dúvida é só perguntar.

Olá @Simon Viegas muito obrigado pela sua resposta foi de grande ajuda e fácil compreensão, consegui entender um pouco do raciocínio como uma função chama a outra que é a si mesma até ela atingir seu caso base.

 Se (n = 1) então
   retorne v [n]

na linha acima a função recursiva atinge o seu caso base certo ?

A dúvida que me ficou é a seguinte: neste exemplo, assim que função recursiva atingir o seu caso base eu sei que ela retornaria 30 pois seria (SVR3([30,20,10], 1). Então finalizaria a função recursiva voltando para o algoritmo e atribuiria para variável s o valor 30? Ou quando a função atingir o seu caso base ela retornaria a suas funções recursivas anteriores que foram chamadas SVR2([30,20,10], 2) e SVR1([30,20,10], 3) e só depois voltaria para o algoritmo e atribuiria para a variável s o valor 60?

desde já grato sua explicação foi excelente.

Simon Viegas · 30 de maio de 2019

7 horas atrás, Primon disse:

A dúvida que me ficou é a seguinte: neste exemplo, assim que função recursiva atingir o seu caso base eu sei que ela retornaria 30 pois seria (SVR3([30,20,10], 1). Então finalizaria a função recursiva voltando para o algoritmo e atribuiria para variável s o valor 30? Ou quando a função atingir o seu caso base ela retornaria a suas funções recursivas anteriores que foram chamadas SVR2([30,20,10], 2) e SVR1([30,20,10], 3) e só depois voltaria para o algoritmo e atribuiria para a variável s o valor 60?

Ao finalizar (SVR3([30,20,10], 1), o programa vai voltar exatamente para o ponto onde (SVR3([30,20,10], 1) foi invocado, ou seja, lá dentro de (SVR2([30,20,10], 2). Usando um pouca da abstração, lá estaria com algo assim:

//dentro de  (SVR2([30,20,10], 2) estaria com algo assim
retorne v [n] + (SVR3([30,20,10], 1)

Como v[n] = [2] = 20... e (SVR4([30,20,10], 3) retornou 30, seria equivalente a:

//dentro de  (SVR2([30,20,10], 2) estaria com algo assim
retorne 20 + 30

Entende?

Aí a função (SVR1([30,20,10], 3), que invocou o (SVR2([30,20,10], 2), vai receber o que esta segunda função retornou nela.. lá (SVR1([30,20,10], 3) segue o mesmo fluxo... e por aí vai.

Essas chamadas de funções vão ficando em uma pilha. Algo como:

(SVR3([30,20,10], 1)
(SVR2([30,20,10], 2)
(SVR1([30,20,10], 3)
(processaVetor)

Quando lá no programa principal é invocado qualquer método (função ou procedimento), o ponto onde foi invocado fica salvo... aí entra nessa função que acabou de invocar... Essa nova função fica uma posição acima na pilha... faz o que tem que fazer e volta. No contexto do seu algoritmo, o programa principal invocará uma função. Aí essa nova função fica acima do programa principal. Acontece que essa nova vai invocar uma 2ª função... que vai ficar acima da primeira. A 2ª vai invocar a 3ª... e por aí vai. Quando a função que está no topo (a 3) termina, volta para exatamente o ponto onde a função anterior (a 2) o chamou. Vai continuar o fluxo normal na 2, que já é terminar também.. daí vai voltar para 1ª, que vai terminar que volta para o programa principal que também vai seguir o fluxo normalmente... atribuindo o retorno a s, posteriormente escrevendo na tela e depois finalizando.

ADENDO:

Verifique se no seu programa que compila o código tem um recurso de "passo a passo". No Portugol Studio tem duas "solas de sapatos", acho que a tela é shift+F5... cada vez que vai pressionando, vai seguindo o fluxo do código... No VisualG sei que é a tecla F8.

adicionado 8 minutos depois

Em relação a questão de "caso base" em não sei como seria esse conceito.. mas é basicamente isso. A função e os parâmetros usados nela tem que funcionar de forma que uma hora a função pare de invocar uma nova.

Uma função recursiva é exatamente igual a uma função como outra qualquer.. apenas é estruturada de uma forma específica.. a vantagem da recursividade é que você não precisa criar um monte de cópias... se não pudesse invocar a própria função, teria que sair replicando...

Primon · 30 de maio de 2019

3 horas atrás, Simon Viegas disse:
Ao finalizar (SVR3([30,20,10], 1), o programa vai voltar exatamente para o ponto onde (SVR3([30,20,10], 1) foi invocado, ou seja, lá dentro de (SVR2([30,20,10], 2). Usando um pouca da abstração, lá estaria com algo assim:
//dentro de  (SVR2([30,20,10], 2) estaria com algo assim
retorne v [n] + (SVR3([30,20,10], 1)
Como v[n] = [2] = 20... e (SVR4([30,20,10], 3) retornou 30, seria equivalente a:
//dentro de  (SVR2([30,20,10], 2) estaria com algo assim
retorne 20 + 30
Entende?

Aí a função (SVR1([30,20,10], 3), que invocou o (SVR2([30,20,10], 2), vai receber o que esta segunda função retornou nela.. lá (SVR1([30,20,10], 3) segue o mesmo fluxo... e por aí vai.

Essas chamadas de funções vão ficando em uma pilha. Algo como:
(SVR3([30,20,10], 1)
(SVR2([30,20,10], 2)
(SVR1([30,20,10], 3)
(processaVetor)
Quando lá no programa principal é invocado qualquer método (função ou procedimento), o ponto onde foi invocado fica salvo... aí entra nessa função que acabou de invocar... Essa nova função fica uma posição acima na pilha... faz o que tem que fazer e volta. No contexto do seu algoritmo, o programa principal invocará uma função. Aí essa nova função fica acima do programa principal. Acontece que essa nova vai invocar uma 2ª função... que vai ficar acima da primeira. A 2ª vai invocar a 3ª... e por aí vai. Quando a função que está no topo (a 3) termina, volta para exatamente o ponto onde a função anterior (a 2) o chamou. Vai continuar o fluxo normal na 2, que já é terminar também.. daí vai voltar para 1ª, que vai terminar que volta para o programa principal que também vai seguir o fluxo normalmente... atribuindo o retorno a s, posteriormente escrevendo na tela e depois finalizando.

ADENDO:

Verifique se no seu programa que compila o código tem um recurso de "passo a passo". No Portugol Studio tem duas "solas de sapatos", acho que a tela é shift+F5... cada vez que vai pressionando, vai seguindo o fluxo do código... No VisualG sei que é a tecla F8.

adicionado 8 minutos depois

Em relação a questão de "caso base" em não sei como seria esse conceito.. mas é basicamente isso. A função e os parâmetros usados nela tem que funcionar de forma que uma hora a função pare de invocar uma nova.

Uma função recursiva é exatamente igual a uma função como outra qualquer.. apenas é estruturada de uma forma específica.. a vantagem da recursividade é que você não precisa criar um monte de cópias... se não pudesse invocar a própria função, teria que sair replicando...

@Simon Viegas Ufa muito obrigado, agora consegui entender como isso funciona, para iniciante achei algo bem complexo mas acredito que com a prática esse conceito vai melhorando =D. O "caso base" é apenas um termo que é utilizado no meu livro da faculdade para fazer isso que você disse "A função e os parâmetros usados nela tem que funcionar de forma que uma hora a função pare de invocar uma nova." quando a função parar de invocar uma nova função ela atingiu o caso base, muito obrigado por sua explicação nota 10.