Os números de Pell são definidos pela seguinte recursão
p(n)= \begin{cases}0 & \text { se } n=0 \\\\ 1 & \text { se } n=1 \\\\ 2 p(n-1)+p(n-2) & \text { se } n>2\end{cases}
Alguns números desta sequência são: 0,1,2,5,12,29,70,169,408,985 \ldots
Faça uma função recursiva que receba um número N e retorne o N -ésimo número de Pell.

Passo 1

O enunciado pede uma função recursiva que, dado um inteiro N, retorne o N-ésimo número de Pell. A sequência de Pell é definida pelos casos-base
p(0)=0,\quad p(1)=1
e pela relação de recorrência
p(n)=2\,p(n-1)+p(n-2),\quad n\ge2.
Para resolver, vamos traduzir exatamente essa definição em código: detectar os casos-base e, caso contrário, chamar a própria função para n-1 e n-2.

Passo 2

Definir os casos-base da recursão para evitar chamadas infinitas:
  • Se n=0, retorna 0.
  • Se n=1, retorna 1.

Passo 3

Implementar o passo recursivo usando a relação
p(n)=2\,p(n-1)+p(n-2).
Ou seja, para n\ge2 a função chama a si mesma com n-1 e n-2 e faz 2 vezes o primeiro mais o segundo.

Passo 4

Colocar tudo junto numa função em Python. Vai ficar assim:
def pell(n):
    """
    Retorna o n-ésimo número de Pell:
    p(\(0\))\(=0\), p(\(1\))\(=1\), p(n)\(=2\)*p(n-\(1\))\(+\)p(n-\(2\)) para n>\(=2\).
    """
    if n \(==0\):
        return \(0\)
    if n \(==1\):
        return \(1\)
    return \(2\) * pell(n-\(1\)) \(+\) pell(n-\(2\))

Passo 5

Podemos testar alguns valores para conferir:
print([pell(i) for i in range(\(10\))])
# Saída: [\(0\), \(1\), \(2\), \(5\), \(12\), \(29\), \(70\), \(169\), \(408\), \(985\)]

Resposta

def pell(n):
    """
    Retorna o n-ésimo número de Pell:
    p(\(0\))\(=0\), p(\(1\))\(=1\), p(n)\(=2\)*p(n-\(1\))\(+\)p(n-\(2\)) para n>\(=2\).
    """
    if n \(==0\):
        return \(0\)
    if n \(==1\):
        return \(1\)
    return \(2\) * pell(n-\(1\)) \(+\) pell(n-\(2\))

Exercícios relacionados