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 ( 1,1,2,3,5,8,13,21,34,55 ldots…).
F1=1 F2=1 F3=2 F4=1+2=3 F5=2+3=5

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:
  1. Entender o que é recursão (função que chama a si mesma).
  2. Identificar os casos base (quando parar a recursão).
  3. Montar a chamada recursiva baseada na definição Fn = 1, & se n = 1 ou n = 2, Fn-1 + Fn-2, & se n > 2

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:
  1. Entrada: um número inteiro Fn = Fn-1 + Fn-2 , a posição na série.
  2. Saída: , o valor do termo na posição .
  3. Casos base:
    • Se → retorno 1.
    • Se → retorno 1.
  4. 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:
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,
  1. fibonacci(5) chama fibonacci(4) + fibonacci(3)
  2. fibonacci(4) = fibonacci(3) + fibonacci(2)
  3. fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
  4. 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)

Exercícios relacionados