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);
}

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).

Passo 3

Expandindo passo a passo a pilha de chamadas:
  1. Empilha misterio(4)
  2. Dentro de misterio(4), empilha misterio(3)
  3. Dentro de misterio(3), empilha misterio(2) — é caso-base, retorna 2 e desempilha
  4. Ainda em misterio(3), empilha misterio(1) — é caso-base, retorna 1 e desempilha
  5. Calcula retorno de misterio(3):
misterio(3)=misterio(2)+3cdot misterio(1)=2+3cdot1=5
desempilha misterio(3)
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):
misterio(4)=misterio(3)+4cdot misterio(2)=5+4cdot2=13

Passo 5

Ao final, a pilha fica vazia e a função retorna 13.

Resposta

Sequência de empilhamentos e desempilhamentos:
  1. [misterio(4)]
  2. [misterio(4), misterio(3)]
  3. [misterio(4), misterio(3), misterio(2)] → retorna 2 → desempilha
  4. [misterio(4), misterio(3), misterio(1)] → retorna 1 → desempilha
  5. [misterio(4), misterio(3)] → retorna 5 → desempilha
  6. [misterio(4), misterio(2)] → retorna 2 → desempilha
  7. [misterio(4)] → retorna 13 → desempilha (pilha vazia)
Valor retornado por misterio(4): 13

Exercícios relacionados