Desenvolva um algoritmo usando modularização, especificamente funções recursivas para compor a séria de Fibonacci de um termo. A sequência de Fibonacci é um padrão numérico em que o primeiro e o segundo termo são iguais a 1 e cada termo a partir do terceiro é a soma dos dois termos anteriores. essa sequência é infinita e crescente. Utilizando a notação de sequência, expressamos a sequência de Fibonacci por (
…).
Passo 1
Beleza, resumindo: a questão pede pra gente criar um algoritmo “modularizado” (ou seja, usando função separada) que calcule o n-ésimo termo da série de Fibonacci via recursão. Matéria envolvida: recursão em funções. O que vamos precisar:
- Entender o que é recursão (função que chama a si mesma).
- Identificar os casos base (quando parar a recursão).
- Montar a chamada recursiva baseada na definição
Passo 2
Teoria da recursão:
- Uma função recursiva precisa de casos base (onde ela não se chama de novo) para evitar loop infinito.
- E de casos recursivos, onde ela se chama para resolver subproblemas menores.
No nosso cenário: - Casos base:
e → retornam 1. - Caso recursivo: para
, devolver .
Passo 3
Identificando cada parte:
- Entrada: um número inteiro
, a posição na série. - Saída:
, o valor do termo na posição . - Casos base:
- Se
→ retorno 1. - Se
→ retorno 1.
- Se
- Recorrência:
A função vai chamar a si mesma para calcular esses dois valores menores.
Passo 4
Implementando a função recursiva “fibonacci”:
Pseudocódigo (estilo Python) comentado linha a linha:
Pseudocódigo (estilo Python) comentado linha a linha:
função fibonacci(n):
se n == 1 ou n == 2: # caso base
retorna 1
senão: # caso recursivo
return fibonacci(n-1) + fibonacci(n-2)
Comentários:
- Na linha do
se
, garantimos que a recursão tem onde parar. - No
senão
, chamamos duas vezes a própria função, reduzindo o problema de “n” para “n–1” e “n–2”.
Passo 5
Modularizando num programa principal:
função principal():
lê inteiro n do usuário
resultado = fibonacci(n) # chama a função recursiva
imprime resultado
Dessa forma, o algoritmo está separado em “módulos”:
- Um módulo cuida da lógica de leitura e impressão (principal).
- Outro módulo faz o cálculo (fibonacci).
Passo 6
Testando mentalmente: se
n = 5
,- fibonacci(5) chama fibonacci(4) + fibonacci(3)
- fibonacci(4) = fibonacci(3) + fibonacci(2)
- fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
- fibonacci(2) = 1 (caso base)
… e assim vai, você chega em 5.
Resposta
função fibonacci(n):
se n == 1 ou n == 2:
retorna 1
senão:
retorna fibonacci(n-1) + fibonacci(n-2)
função principal():
lê inteiro n
imprime fibonacci(n)