Teste de mesa c/ Recursividade!

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

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.

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

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.

paulo1205
(usa Ubuntu)

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

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.



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.

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.