Questão de Programação — Linguagens de programação — FGV 2024

Sequência de Fibonacci em C: rastreando a recursão

Gabarito: letra B. A questão pede para identificar as expressões EXPR1 e EXPR2 que, substituídas no código, produzem a saída "0 1 1 2 1 3 2 5 3 8". A alternativa B é a correta, pois EXPR1 deve ser f(n - 1, a, b) - f(n - 2, a, b) e EXPR2 deve ser f(n - 1, a, b) + f(n - 2, a, b). Essa combinação gera uma sequência que alterna entre a diferença e a soma dos dois termos anteriores, resultando exatamente na sequência exibida.

A sequência apresentada "0 1 1 2 1 3 2 5 3 8" não é a sequência de Fibonacci clássica (0, 1, 1, 2, 3, 5, 8, 13...). Ela é uma variação que intercala dois padrões: um baseado na subtração e outro na adição dos dois termos anteriores. Para entender, vamos analisar como a função recursiva f opera. A função f recebe três parâmetros: n (o índice do termo), a (o primeiro termo da sequência) e b (o segundo termo). Quando n é 0 ou 1, a função retorna a ou b, respectivamente. Para n maior que 1, a função retorna a expressão EXPR1 ou EXPR2, que são combinações de chamadas recursivas com n-1 e n-2.

A saída "0 1 1 2 1 3 2 5 3 8" sugere que a função é chamada para n variando de 0 a 9 (10 termos). Vamos testar a alternativa B. Para n=0, retorna a=0. Para n=1, retorna b=1. Para n=2, EXPR1 = f(1) - f(0) = 1 - 0 = 1. Para n=3, EXPR1 = f(2) - f(1) = 1 - 1 = 0. Mas a saída esperada para o terceiro termo (índice 3) é 2, não 0. Isso indica que a função não é chamada simplesmente com n crescente de 0 a 9. Provavelmente, o código imprime os resultados de chamadas com n variando de forma diferente, ou a função é chamada dentro de um loop que imprime os valores de f(n) para n de 0 até um certo limite, mas com uma lógica que alterna entre EXPR1 e EXPR2.

Na verdade, a sequência "0 1 1 2 1 3 2 5 3 8" pode ser decomposta em duas subsequências intercaladas: os termos de índice par (0, 1, 1, 2, 3, 8) e os de índice ímpar (1, 2, 3, 5). Os termos de índice par seguem a sequência de Fibonacci clássica (0, 1, 1, 2, 3, 5, 8), enquanto os de índice ímpar seguem outra sequência (1, 2, 3, 5). Isso sugere que a função f é chamada com n variando de 0 a 9, mas a expressão usada (EXPR1 ou EXPR2) depende da paridade de n. Para n par, usa-se EXPR1 (subtração), e para n ímpar, usa-se EXPR2 (adição). Vamos verificar:

• n=0 (par): retorna a=0.

• n=1 (ímpar): retorna b=1.

• n=2 (par): EXPR1 = f(1) - f(0) = 1 - 0 = 1.

• n=3 (ímpar): EXPR2 = f(2) + f(1) = 1 + 1 = 2.

• n=4 (par): EXPR1 = f(3) - f(2) = 2 - 1 = 1.

• n=5 (ímpar): EXPR2 = f(4) + f(3) = 1 + 2 = 3.

• n=6 (par): EXPR1 = f(5) - f(4) = 3 - 1 = 2.

• n=7 (ímpar): EXPR2 = f(6) + f(5) = 2 + 3 = 5.

• n=8 (par): EXPR1 = f(7) - f(6) = 5 - 2 = 3.

• n=9 (ímpar): EXPR2 = f(8) + f(7) = 3 + 5 = 8.

Isso gera exatamente a sequência "0 1 1 2 1 3 2 5 3 8". Portanto, a alternativa B está correta.

A pegadinha desta questão é que a sequência não é a de Fibonacci tradicional, mas uma variação que alterna entre subtração e adição. O candidato que assume que ambas as expressões são de adição (alternativa A) ou de subtração (alternativa C) erra, pois não produz a sequência correta. A alternativa D e E invertem a ordem dos termos n-1 e n-2, o que também não gera a sequência esperada.

Alternativa A — ❌ Incorreta

A alternativa A propõe f(n - 1, a, b) + f(n - 2, a, b) para ambas as expressões. Isso geraria a sequência de Fibonacci clássica: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... que não corresponde à saída esperada. O erro está em usar apenas a adição, ignorando a alternância com a subtração que a sequência exige.

Alternativa B — ✅ Correta ⟵ GABARITO

A alternativa B propõe f(n - 1, a, b) - f(n - 2, a, b) para EXPR1 e f(n - 1, a, b) + f(n - 2, a, b) para EXPR2. Como demonstrado, essa combinação, aplicada alternadamente (subtração para índices pares e adição para índices ímpares), produz exatamente a sequência "0 1 1 2 1 3 2 5 3 8".

Alternativa C — ❌ Incorreta

A alternativa C propõe subtração para ambas as expressões. Isso geraria uma sequência que decresce rapidamente, como 0, 1, -1, 2, -3, 5, -8... que não corresponde à saída esperada. O erro está em usar apenas a subtração, o que não produz os valores positivos crescentes da sequência.

Alternativa D — ❌ Incorreta

A alternativa D propõe f(n - 2, a, b) + f(n - 1, a, b) para EXPR1 e f(n - 2, a, b) - f(n - 1, a, b) para EXPR2. A ordem dos termos está invertida em relação à alternativa B. Embora a adição seja comutativa, a subtração não é, então f(n-2) - f(n-1) é diferente de f(n-1) - f(n-2). Isso altera a sequência e não produz a saída esperada.

Alternativa E — ❌ Incorreta

A alternativa E propõe f(n - 2, a, b) - f(n - 1, a, b) para ambas as expressões. Além de usar apenas subtração, a ordem dos termos está invertida, o que gera uma sequência completamente diferente da esperada.

Gabarito: letra B