Teste de mesa c/ Recursividade!

1. Teste de mesa c/ Recursividade!

Daniel Marchi
dms_

(usa elementary OS)

Enviado em 25/09/2013 - 17:50h

Boa Tarde, estou com dúvida de como realizar um teste de mesa no seguinte código:



int f1(int n) {

   if(n == 0) return 1;

   if(n == 1) return 1;

   return f1(n-1) + 2 * f1(n-­2);

}


obrigado


  


2. Re: Teste de mesa c/ Recursividade!

Paulo
paulo1205

(usa Ubuntu)

Enviado em 25/09/2013 - 18:41h

"Teste de mesa" é o mesmo que "método do chinês" (i.e.: executar o algoritmo mentalmente, com apoio, no máximo, de papel e lápis)?

Se for, não vi qual sua dúvida.

No entanto, uma coisa eu vi: aquelas variáveis n1 e n2 não aparecem declaradas nem definidas em lugar algum. Como a condição para o fim do ciclo de recursividade é que f1() seja chamada com um parâmetro com valor 0 ou 1, e como o corpo da função não altera os eventuais valores de n1 e n2, que são usados como parâmetros das chamadas recursivas, é razoável supor que a execução vai entrar em loop infinito.


3. Re: Teste de mesa c/ Recursividade!

Daniel Marchi
dms_

(usa elementary OS)

Enviado em 25/09/2013 - 18:44h

Vish, vocÊ está a 100km/h e eu a 10km/h, kkk, valeu a explicação. Tenho mesmo é que estudar mais até...eu sei a definição de teste de mesa, mas estava com dúvidas de como empregar neste algoritmo.


@edit, eu postei o código errado, desculpe! Acho era n-1 ao invés de n1


4. Re: Teste de mesa c/ Recursividade!

Kaio Vinicius Cassiano dos Santos
kaiio_

(usa Debian)

Enviado em 26/09/2013 - 16:43h

Teste de mesa é o seguinte: você opera o programa, vendo suas funcionalidades, o que ocorre. Obviamente, deve-se conhecer as funções do programa.
Por exemplo, no seu caso existe a variável n.
Então, atribua um valor a ela, por exemplo 1.

Não "cai" no primeiro if, cai no segundo, e retorna 1.
Ok, fim do programa.

Atribua 0.
"Cai" no primeiro if, retorna 1.

Atribua 2.
Passa pelos 2 ifs, faz a operação 2(2-1)*2(2-2)
2*(1)*2*(2-2)
2*(1)*2*(0)
2*2*0
4*0
0

Atribua 3
3*(3-1)*3(3-2)
3*(2)*3*(3-2)
3*(2)*3*(1)
6*3*1
18*1
18

Certo?

E por ai vai. Qual seria a função do seu programa?

Tem um caso fácil, é o seguinte: retorna os valores anteriores ao número inserido, até 0.

void down(int n)
{
if(n<1)
{
return;
}
else
{
printf("%d\n",n);
down(n-1);
}
}

E tem o contrário, que vai de 0 até o número informado:

void up(int n)
{
if(n<1)
{
return;
}
else
{
up(n-1);
printf("%d\n",n);
}
}

Esse nomedafunção(n-1) antes e depois do printf é a diferença.

O teste de mesa do down, por exemplo, seria assim:

n = 3

Não "cai" no primeiro if, então, imprime 3 na tela e n passa a valer 2 (n-1)

Passa pelo if novamente, imprime 2 na tela e n passa a valer 1 (n-1)

Não cai no primeiro if, então, imprime 1 na tela e n passa a valer 0 (n-1)

"Cai" no primeiro if, não retorna nada e sai da função.

Entendido? Qualquer coisa msg ou responde esse fórum, vou dar uma acompanhada.


5. Re: Teste de mesa c/ Recursividade!

Paulo
paulo1205

(usa Ubuntu)

Enviado em 27/09/2013 - 11:08h

kaiio_ escreveu:

Teste de mesa é o seguinte: você opera o programa, vendo suas funcionalidades, o que ocorre. Obviamente, deve-se conhecer as funções do programa.
Por exemplo, no seu caso existe a variável n.
Então, atribua um valor a ela, por exemplo 1.

Não "cai" no primeiro if, cai no segundo, e retorna 1.
Ok, fim do programa.

Atribua 0.
"Cai" no primeiro if, retorna 1.

Atribua 2.
Passa pelos 2 ifs, faz a operação 2(2-1)*2(2-2)
2*(1)*2*(2-2)
2*(1)*2*(0)
2*2*0
4*0
0


Aqui você errou. Não é "2*(2-1)*2*(2-2)", mas sim "f1(2-1)+2*f1(2-2)", que resulta em f1(1)+2*f1(0) => 1+2*1 => 1+2 => 3.

Atribua 3
3*(3-1)*3(3-2)
3*(2)*3*(3-2)
3*(2)*3*(1)
6*3*1
18*1
18

Certo?


Errado. O certo para n=3 seria o que segue.

f1(n-1)+2*f1(n-2) =
f1(3-1)+2*f1(3-2) =
f1(2)+2*f1(1) = # f1(2) foi calculado acima
3+2*1 =
3+2 =
5


O teste será facilitado se você usar o valor das rodadas anteriores para calcular a expressão das rodadas seguintes, à medida em que se for aumentando o valor do parâmetro. Não é o que vai acontecer na realidade: o computador não vai ter já guardados os valores de f1(4998) e f1(4999) quanto for chamado com f1(5000).

Na verdade, mesmo muito antes disso, a coisa já começa a ficar complicada. Veja o que o computador realmente executa quando você chama f1(5).

f1(5)                                                                               =
f1(4) + 2*f1(3) =
(f1(3) + 2*f1(2) ) + 2*(f1(2) + 2*f1(1)) =
((f1(2) + 2*f1(1)) + 2*(f1(1)+2*f1(0))) + 2*((f1(1) + 2*f1(0)) + 2*1 ) =
(((f1(1)+2*f1(0)) + 2*1 ) + 2*(1 +2*1 )) + 2*((1 + 2*1 ) + 2 ) =
(((1 +2*1 ) + 2 ) + 2*(1 +2 )) + 2*((1 + 2 ) + 2 ) =
(((1 +2 ) + 2 ) + 2*3 ) + 2*(3 + 2 ) =
((3 + 2 ) + 6 ) + 2*5 =
(5 + 6 ) + 10 =
11 + 10 =
21


Ou seja: a chamada a f1() com o parâmetro 5 se desdobrou em 14 chamadas internas recursivas. Se o parâmetro fosse 6, teriam sido 22 chamadas recursivas. 7 acarretaria 36 chamadas recursivas; 8, 58; e assim sucessivamente, sendo que a maior parte dessas chamadas é recalculando os mesmos valores de chamadas anteriores.

Mas eu acho que não é isso (i.e. análise de complexidade) o que se quer. O que mais importa, principalmente quando se tem recursão, é ter a certeza de que o algoritmo será finito.

No caso dele, ser finito tem um pré-requisito de domínio: o parâmetro não pode ser negativo.


6. Re: Teste de mesa c/ Recursividade!

Kaio Vinicius Cassiano dos Santos
kaiio_

(usa Debian)

Enviado em 30/09/2013 - 17:04h

Cara, eu fiz isso correndo no meu horário de trabalho, por isso pedi pra verificarem. Mesmo assim obrigado pela correção.






Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts