¿Lucas, Fibo, que hacéis con una Pytón?

Recientemente he aprendido que existe una sucesión muy "parecida" a la famosísima sucesión de Fibonacci: se trata de la sucesión de Lucas.

La sucesión de Fibonacci se obtiene comenzando con 0 y 1, y para los siguientes números, simplemente se suman los dos anteriores:

0, 1, 1, 2, 3, 5, 8, 13, 21...

La sucesión de Lucas se obtiene comenzando con 2 y 1, y al igual que con la sucesión de Fibonacci, se suman las dos posiciones anteriores para cada nueva posición.

2, 1, 3, 4, 7, 11, 18, 29, 47...

Si lo implementamos en Python, tendremos dos funciones muy similares:

"""Sucesión de Lucas.
   :param n: La posición del número a calcular.
   :return: Una lista con las n primeras posiciones de Lucas.
"""
lucas = lambda n: \
            [] if n < 0 else \
            [2] if n == 0 else \
            [2, 1] if n == 1 else \
            (l_lucas := lucas(n - 1)) + [l_lucas[-1] + l_lucas[-2]]

"""Sucesión de Fibonacci.
   :param n: La posición del número a calcular.
   :return: Una lista con las n primeras posiciones de Fibonacci.
"""
fibo = lambda n: \
            [] if n < 0 else \
            [0] if n == 0 else \
            [0, 1] if n == 1 else \
            (l_fibo := fibo(n - 1)) + [l_fibo[-1] + l_fibo[-2]]

Para obtener las listas con las sucesiones empleamos lambdas, la expresión if, y el nuevo operador de asignación, de manera que solo tengamos que calcular la lista anterior una sola vez.

En el enlace anterior puedes aprender sobre este operador, solo tienes que bajar casi hasta el final.

Como ya sabemos, la forma de trabajar con lambdas es emplear la recursividad cada vez que queramos algo parecido a un bucle. La recursividad solo funciona si tenemos un caso base (las dos posiciones iniciales n == 0 y n == 1), y un caso normal (el resto de posiciones para n > 1).

Añadimos un caso base "extra" (n < 0), por si se da el caso de algún usuario "travieso".

La forma de generar ambas sucesiones es muy similar. Para ambas tenemos dos valores iniciales, que deben ser devueltos si intentamos obtener las dos primeras posiciones: es decir, la 0 y la 1.

A partir de ahí, simplemente concatenamos la lista anterior con la suma de las posiciones última y penúltima de dicha lista.

De hecho... son demasiado parecidas... ¿no podríamos crear una función única, que tomase como parámetro las dos primeras posiciones de la sucesión a generar? Ya de paso, ¿podemos crear una función a la que se le pasen las n primeras posiciones de la lista inicial de una sucesión para generar los números de Lucas, de Fibonacci, y de Tribonacci?

Veamos, la función succ() solo hay que devolver, dada una lista inicial l_init y su número de posiciones len_l_init...

• para n < 0, la lista vacía, []
• para n < i, la lista l_init hasta n + 1 (porque los índices en Python comienzan en 0): l_init[:n + 1]
• para el resto de casos n >= len_l_init,
  • se calcula la lista para succ(n - 1), y se calcula el nuevo elemento, que es el resultado de sumar las len_l_init últimas posiciones.

Pues ya lo tenemos. Como el código ya es más
complicado que un par de líneas, crearemos una función "de verdad".

def succ(l_init, n):
    """
        Sucesión genérica.
        :param l: La lista inicial de valores.
        :param n: La posición del número a calcular.
        :return: Una lista con las n primeras posiciones de Lucas, Fibonacci o Tribonacci.
    """
    len_l_init = len(l_init)
    toret = []

    match n:
        case _ if n < 0:
            toret = []
        case _ if n < len_l_init:
            toret = l_init[:n + 1]
        case _:
            # Sucesión hasta la posición anterior
            toret = succ(l_init, n - 1)

            # Calcula la nueva posición
            toret += [sum(toret[-len_l_init:])]

    return toret

¡Python mola!

Estamos empleando la nueva estructura de pattern matching, que, para que nos entendamos, hablando mal y rápido es como switch en C, pero mucho más potente. Aquí solo empleamos una fracción de sus capacidades, concretamente le añadimos condiciones a las etiquetas de los primeros dos casos. Sustituimos el nombre de lo que sería la nueva variable por _ porque en realidad, no nos interesa, ya lo tenemos en n.

Utilicemos el código:

def main():
    for i in range(-1, 10):
        print(f"Succ Fibo - {succ([0, 1], i)=}")

    print()

    for i in range(-1, 10):
        print(f"Succ Lucas - {succ([2, 1], i)=}")


if __name__ == "__main__":
    main()

Y efectivamente, el resultado es:

ucc Fibo - succ([0, 1], i)=[]
Succ Fibo - succ([0, 1], i)=[0]
Succ Fibo - succ([0, 1], i)=[0, 1]
Succ Fibo - succ([0, 1], i)=[0, 1, 1]
Succ Fibo - succ([0, 1], i)=[0, 1, 1, 2]
Succ Fibo - succ([0, 1], i)=[0, 1, 1, 2, 3]
Succ Fibo - succ([0, 1], i)=[0, 1, 1, 2, 3, 5]
Succ Fibo - succ([0, 1], i)=[0, 1, 1, 2, 3, 5, 8]
Succ Fibo - succ([0, 1], i)=[0, 1, 1, 2, 3, 5, 8, 13]
Succ Fibo - succ([0, 1], i)=[0, 1, 1, 2, 3, 5, 8, 13, 21]
Succ Fibo - succ([0, 1], i)=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Succ Lucas - succ([2, 1], i)=[]
Succ Lucas - succ([2, 1], i)=[2]
Succ Lucas - succ([2, 1], i)=[2, 1]
Succ Lucas - succ([2, 1], i)=[2, 1, 3]
Succ Lucas - succ([2, 1], i)=[2, 1, 3, 4]
Succ Lucas - succ([2, 1], i)=[2, 1, 3, 4, 7]
Succ Lucas - succ([2, 1], i)=[2, 1, 3, 4, 7, 11]
Succ Lucas - succ([2, 1], i)=[2, 1, 3, 4, 7, 11, 18]
Succ Lucas - succ([2, 1], i)=[2, 1, 3, 4, 7, 11, 18, 29]
Succ Lucas - succ([2, 1], i)=[2, 1, 3, 4, 7, 11, 18, 29, 47]
Succ Lucas - succ([2, 1], i)=[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]