Mostrar a pilha de execução e o valor retornado por misterio(4), considerando que a função misterio é implementada como:
int misterio(int n)
{
if ((n == 1) || (n == 2))
return n;
else
return misterio(n-1) + n*misterio(n-2);
}
int misterio(int n)
{
if ((n == 1) || (n == 2))
return n;
else
return misterio(n-1) + n*misterio(n-2);
}
Passo 1
O enunciado pede para mostrar a pilha de execução (stack) da função recursiva e o valor de retorno de misterio(4). O conteúdo é recursão com caso-base e caso recursivo. Para resolver, precisamos entender como as chamadas são empilhadas e desempilhadas, e como calcular cada retorno.
Passo 2
Identificamos os casos-base: quando n == 1 retorna 1 e quando n == 2 retorna 2. Para n = 4 (não é caso-base), aplicamos a regra recursiva:
misterio(4) = misterio(3) + 4 · misterio(2)
Começamos empilhando a chamada misterio(4).
misterio(4) = misterio(3) + 4 · misterio(2)
Começamos empilhando a chamada misterio(4).
Passo 3
Expandindo passo a passo a pilha de chamadas:
- Empilha misterio(4)
- Dentro de misterio(4), empilha misterio(3)
- Dentro de misterio(3), empilha misterio(2) — é caso-base, retorna 2 e desempilha
- Ainda em misterio(3), empilha misterio(1) — é caso-base, retorna 1 e desempilha
- Calcula retorno de misterio(3):
desempilha misterio(3)
6. De volta a misterio(4), empilha misterio(2) — retorna 2 e desempilha
6. De volta a misterio(4), empilha misterio(2) — retorna 2 e desempilha
Passo 4
Agora, com misterio(3)=5 e misterio(2)=2, calculamos misterio(4):
Passo 5
Ao final, a pilha fica vazia e a função retorna 13.
Resposta
Sequência de empilhamentos e desempilhamentos:
- [misterio(4)]
- [misterio(4), misterio(3)]
- [misterio(4), misterio(3), misterio(2)] → retorna 2 → desempilha
- [misterio(4), misterio(3), misterio(1)] → retorna 1 → desempilha
- [misterio(4), misterio(3)] → retorna 5 → desempilha
- [misterio(4), misterio(2)] → retorna 2 → desempilha
- [misterio(4)] → retorna 13 → desempilha (pilha vazia)
Valor retornado por misterio(4): 13