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
.
b) Quantas vezes a função fr é chamada para se obter o valor de
?
int fr( int n ) {
if ( ( n == 1 ) || ( n == 2 ) )
return n;
else
return fr(n-2) + ( n * fr(n-1) );
}
b) Quantas vezes a função fr é chamada para se obter o valor de
Passo 1
O enunciado dá a função recursiva em C abaixo (vou escrever em palavras também para ficar claro):
- Se
é ou , a função retorna . - Caso contrário, a função retorna
.
As perguntas que precisamos responder são:
a) Determinar o valor de .
b) Contar quantas vezes a função é chamada (incluindo chamadas de casos-base) quando se calcula
.
a) Determinar o valor de
b) Contar quantas vezes a função
Informações relevantes que o enunciado dá e que vamos usar:
- Valores base:
e . - Recorrência para
: .
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 com
precisamos calcular valores menores de
. Para usar isso na prova sem erro, faça sempre: (i) identifique se
é 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: e
são retornos imediatos, não causam chamadas adicionais.
Recursão significa que para calcular
Exemplo simples de uso de caso-base:
Passo 3
Vamos calcular
primeiro porque
depende dele. Usando a regra para
:
Substituindo os casos-base
e
:
Repare que aqui fiz duas coisas: (a) identifiquei as chamadas necessárias (
e
); (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
. Pela definição:
Sabemos
(caso-base) e do passo anterior
. Substituindo:
Portanto o valor pedido em (a) é
. Dica para prova: calcule valores intermediários pequenos (
,
, etc.) em sequência — isso evita repetir contas.
Passo 5
Agora a parte b): contar quantas vezes
é chamada ao calcular
. Vamos entender isso como contar nós em uma árvore de chamadas: cada invocação de
conta 1. Se
é caso-base (
ou
), ela conta só 1 e não chama mais nada. Se
, a chamada
faz duas chamadas:
e
.
Definimos
= número de chamadas à função
necessárias para calcular
(contando a chamada inicial). A recorrência para
é:
e para
,
Explicação: o
representa a própria chamada
; as outras duas parcelas contam as chamadas feitas pelas duas chamadas recursivas.
Passo 6
Vamos calcular
passo a passo até
:
Calculemos:
Interpretação prática: ao computar
o número total de invocações da função
(incluindo todas as chamadas recursivas e os casos-base) é
. Se quiser, você pode desenhar a árvore de chamadas e contar os nós para ver que bate com
.