Considere a seguinte função recursiva:
int fr( int n ) {
    if ( ( n == 1 ) || ( n == 2 ) )
        return n;
    else
        return fr(n-2) + ( n * fr(n-1) );
}
a) Determine o valor de \boldsymbol{f} \boldsymbol{r}(4).
b) Quantas vezes a função fr é chamada para se obter o valor de \boldsymbol{f} \boldsymbol{r}(\mathbf{6}) ?

Passo 1

O enunciado dá a função recursiva em C abaixo (vou escrever em palavras também para ficar claro):
  • Se n é 1 ou 2, a função retorna n.
  • Caso contrário, a função retorna \text{fr}(n-2) + n\cdot \text{fr}(n-1).
As perguntas que precisamos responder são:
a) Determinar o valor de \text{fr}(4).
b) Contar quantas vezes a função \text{fr} é chamada (incluindo chamadas de casos-base) quando se calcula \text{fr}(6).
Informações relevantes que o enunciado dá e que vamos usar:
  • Valores base: \text{fr}(1)=1 e \text{fr}(2)=2.
  • Recorrência para n\ge3: \text{fr}(n)=\text{fr}(n-2)+n\cdot\text{fr}(n-1).
Não vou resolver nada ainda aqui — só listei o que foi dado e o que é pedido.

Passo 2

Entendendo como avaliar a função recursiva (mini-aula):
Recursão significa que para calcular \text{fr}(n) com n\ge3 precisamos calcular valores menores de \text{fr}. Para usar isso na prova sem erro, faça sempre: (i) identifique se n é caso-base; (ii) se não for, escreva a expressão em termos de chamadas menores; (iii) calcule essas chamadas menores de baixo para cima (outra estratégia é desenhar a árvore de chamadas).
Exemplo simples de uso de caso-base: \text{fr}(1)=1 e \text{fr}(2)=2 são retornos imediatos, não causam chamadas adicionais.

Passo 3

Vamos calcular \text{fr}(3) primeiro porque \text{fr}(4) depende dele. Usando a regra para n\ge3:
\text{fr}(3)=\text{fr}(1)+3\cdot\text{fr}(2).
Substituindo os casos-base \text{fr}(1)=1 e \text{fr}(2)=2:
\text{fr}(3)=1 + 3\cdot 2 = 1 + 6 = 7.
Repare que aqui fiz duas coisas: (a) identifiquei as chamadas necessárias ( \text{fr}(1) e \text{fr}(2)); (b) substituí seus valores conhecidos e fiz a conta. Sempre que fizer isso em prova, escreva explicitamente cada substituição como acima.

Passo 4

Agora calculamos \text{fr}(4). Pela definição:
\text{fr}(4)=\text{fr}(2)+4\cdot\text{fr}(3).
Sabemos \text{fr}(2)=2 (caso-base) e do passo anterior \text{fr}(3)=7. Substituindo:
\text{fr}(4)=2 + 4\cdot 7 = 2 + 28 = 30.
Portanto o valor pedido em (a) é 30. Dica para prova: calcule valores intermediários pequenos ( \text{fr}(3), \text{fr}(4), etc.) em sequência — isso evita repetir contas.

Passo 5

Agora a parte b): contar quantas vezes \text{fr} é chamada ao calcular \text{fr}(6). Vamos entender isso como contar nós em uma árvore de chamadas: cada invocação de \text{fr}(k) conta 1. Se \text{fr}(k) é caso-base ( k=1 ou 2), ela conta só 1 e não chama mais nada. Se k\ge3, a chamada \text{fr}(k) faz duas chamadas: \text{fr}(k-2) e \text{fr}(k-1).
Definimos T(n) = número de chamadas à função \text{fr} necessárias para calcular \text{fr}(n) (contando a chamada inicial). A recorrência para T(n) é:
T(1)=1,\qquad T(2)=1,
e para n\ge3,
T(n)=1 + T(n-2) + T(n-1).
Explicação: o 1 representa a própria chamada \text{fr}(n); as outras duas parcelas contam as chamadas feitas pelas duas chamadas recursivas.

Passo 6

Vamos calcular T(n) passo a passo até n=6:
Calculemos:
T(1)=1,
T(2)=1,
T(3)=1 + T(1) + T(2) = 1 + 1 + 1 = 3,
T(4)=1 + T(2) + T(3) = 1 + 1 + 3 = 5,
T(5)=1 + T(3) + T(4) = 1 + 3 + 5 = 9,
T(6)=1 + T(4) + T(5) = 1 + 5 + 9 = 15.
Interpretação prática: ao computar \text{fr}(6) o número total de invocações da função \text{fr} (incluindo todas as chamadas recursivas e os casos-base) é 15. Se quiser, você pode desenhar a árvore de chamadas e contar os nós para ver que bate com 15.

Resposta

\text{fr}(4)=30
\text{Número de chamadas para calcular fr}(6)=15ú

Exercícios relacionados