Uma palavra de Fibonacci é definida por
f(n)=b se n=0
f(n)=a se n=1
f(n)=f(n-1)+f(n-2) se n>1
Aqui o símbolo “+” denota a concatenação de duas strings. Esta sequência inicia com as seguintes palavras:
b, a, ab, aba, abaab, abaababa, abaababaabaab, …
Faça uma função recursiva que receba um número Ne e retorne a N -ésima palavra de Fibonacci.

Passo 1

O problema propõe gerar a N-ésima palavra de Fibonacci, definida por f(0)=“b”, f(1)=“a” e, para n>1, f(n)=f(n-1)+f(n-2) (concatenação de strings). Vamos usar recursão pura para implementar isso.

Passo 2

Primeiro tratamos os casos base. Se N for 0, devolvemos “b”; se N for 1, devolvemos “a”. Assim garantimos que a recursão tenha um ponto de parada.

Passo 3

Para N>1, chamamos a função recursivamente para obter f(N-1) e f(N-2) e depois concatenamos esses resultados na ordem correta: f(N) = f(N-1) + f(N-2).

Passo 4

Só precisamos colocar isso dentro de uma função, recebendo N como parâmetro e retornando a string desejada. Note que essa implementação tem custo exponencial, pois recalcula muitas subpalavras repetidas vezes. Em casos práticos, poderíamos usar memoização, mas aqui usamos recursão simples conforme pedido.

Resposta

def fib_word(n):
if n == 0:
return “b”
if n == 1:
return “a”
return fib_word(n-1) + fib_word(n-2)

Exercícios relacionados