Programació dinàmica

Introducció#

Per exemple, per calcular el factorial de 7, el podem calcular multiplicant 7 pel factorial de 6, i el factorial de 6 el podem calcular multiplicant 6 pel factorial de 5, etc.

A continuació tens un algorisme recursiu per calcular el factorial de n:

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

assert factorial(6) == 720

Tots els algorismes recursius es poden transformar en lineals mitjançant un array que guarda els resultats parcials, tal com pots veure a continuació:

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)}"

Encara que un algorisme recursiu sigui molt més senzill d’escriure, i més “entenedor”, els algorismes lineals són molt més ràpids d’executar i no estan limitats per la mida de la pila d’execució del procés.

Per aquest motiu, molts compiladors reescriuen el codi recursiu en lineal de forma automàtica si l’algorisme és “tail-recursive”.