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
definida pelos valores iniciais
e a seguinte relação recursiva
se
Alguns valores da sequência são:
e a seguinte relação recursiva
Alguns valores da sequência são:
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)