Programació dinàmica

Introducción

Por ejemplo para calcular el factorial de 7, podemos calcularlo multiplicando 7 por el factorial de 6, y el factorial de 6 podemos calcularlo multiplicando 6 por el factorial de 5, etc.

A continuación tienes un algoritmo recursivo para calcular el factorial de n:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

assert factorial(6) == 720

Todos los algoritmos recursivos se pueden transformar en lineales mediante un array que guarda los resultados parciales, tal y como puedes ver a continuación:

import numpy as np

def factorial(n):
    array = np.arange(n+1, dtype=np.dtype("int64"))
    array[0] = 1

    for i in range(1, n+1):
        array[i] = array[i-1]*i

    return array[n]

assert factorial(6) == 720, f"n = {factorial(6)}"

Aunque un algoritmo recursivo sea mucho más sencillo de escribir, y más “entendedor”, los algoritmos lineales son mucho más rápidos de ejecutar y no están limitados por el tamaño de la pila de ejecución del proceso.

Por este motivo, muchos compiladores reescriben el código recursivo en lineal de forma automática si el algoritmo es “tail-recursive”.