Turmas - 1º Semestre de 2026
Turmas
1º Semestre de 2026

1. Ybadoo
2. Turmas
3. 1º Semestre de 2026
4. Teoria da Computação
5. Primeira Avaliação
6. Questão 02

Questão 02

Observe a função recursiva a seguir, desenvolvida para a máquina genérica.

função xpto(n)
  se (n <= 1)
    então retornar 1;
    senão retornar xpto(n - 1) + xpto(n - 2);
  fim se
fim função

Considerando-se que essa função sempre será chamada com o valor da variável n pertencendo ao conjunto dos números naturais não nulos (n ∈ ℕ*), o seu valor de retorno será:

A O enésimo termo da sequência de Fibonacci.

B O somatório dos n primeiros números naturais não nulos.

C O enésimo termo da sequência y_k = y_k-1 + k.

D O enésimo termo da sequência y_k = y_k-1 + 2.

E O somatório dos n primeiros números naturais pares não nulos.

Solução da Questão 02

A função apresenta exatamente a definição recursiva clássica da sequência de Fibonacci:

Ponto de parada: para n ≤ 1, retorna 1.

Chamada recursiva: para n > 1, retorna a soma dos dois valores anteriores: xpto(n-1) + xpto(n-2).

Fazendo um teste rápido com os primeiros valores:

xpto(0) = 1

xpto(1) = 1

xpto(2) = xpto(1) + xpto(0) = 1 + 1 = 2

xpto(3) = xpto(2) + xpto(1) = 2 + 1 = 3

xpto(4) = xpto(3) + xpto(2) = 3 + 2 = 5

xpto(5) = xpto(4) + xpto(3) = 5 + 3 = 8

xpto(6) = xpto(5) + xpto(4) = 8 + 5 = 13

xpto(7) = xpto(6) + xpto(5) = 13 + 8 = 21

A sequência gerada (1, 1, 2, 3, 5, 8, 13, 21, ...) corresponde aos termos da sequência de Fibonacci.

As demais alternativas descrevem somatórios ou progressões que não seguem a relação de recorrência T(n) = T(n-1) + T(n-2).

Conforme exposto, a resposta correta é:

A O enésimo termo da sequência de Fibonacci.