Faça uma função recursiva que receba um número N e retorne o N -ésimo termo da sequência de Padovan. A sequência de Padovan é uma sequência de naturais P(n) definida pelos valores iniciais
P(0)=P(1)=p(2)=1
e a seguinte relação recursiva
P(n)=P(n-2)+P(n-3) se n>3
Alguns valores da sequência são: 1,1,1,2,2,3,4,5,7,9,12,16,21,28 ldots

Passo 1

O exercício pede para criar uma função recursiva que, dado um inteiro N, retorne o N-ésimo termo da sequência de Padovan.

Passo 2

Identificamos os casos-base da sequência: P(0)=1, P(1)=1 e P(2)=1. Esses valores devemos tratar diretamente na função para parar a recursão.

Passo 3

Para N>2, a relação recursiva é P(n)=P(n-2)+P(n-3). Ou seja, para calcular P(n) chamamos a função novamente com n-2 e n-3.

Passo 4

Implementamos a função combinando casos-base e chamada recursiva conforme a relação definida.

Resposta

def padovan(n):
    # Casos-base da sequência
    if n == 0 or n == 1 or n == 2:
        return 1
    # Relação recursiva P(n)=P(n-2)+P(n-3)
    return padovan(n-2) + padovan(n-3)

Exercícios relacionados