El triángulo de Pascal y la eficiencia

Aquí hay una solución para el bloque pascal:
pascal(fila)(columna){si(columna=0 or columna=fila){reportar(1)} sino{reportar(pascal(fila-1)(columna-1) + pascal(fila-1)(columna))}}

Hay dos casos base, el principio y el final de una fila. El caso recursivo calcula la suma de dos valores en la fila anterior.

pascal(14)(5) = pascal(13)(4) + pascal(13)(5)

Estás a punto de averiguar cuántas llamadas recursivas se necesitan para calcular un valor en el triángulo de Pascal.

¿Qué podrías insertar dentro del bloque para rastrear esto?
  1. Modifica tu bloque pascal para llevar la cuenta de cuántas veces se ejecuta el bloque.
  2. ¿Cuántas veces se llama al bloque pascal al calcular pascal(14)(5)?
  3. ¿Qué ocurre cuando llamas a pascal(20)(5)?
Rastrea a qué llama en realidad pascal(14)(5) para ver la redundancia.

Muchas de las llamadas recursivas son redundantes. Por ejemplo: pascal(14)(5) llamará a pascal(10)(3) muchas veces, pidiendo la misma información.

Esta técnica se llama memoización. Esto no es un error tipográfico; no hay "r" en la palabra. Cada respuesta grabada es como un "memorándum".
  1. Usa una estructura de lista para realizar un seguimiento de los valores ya calculados de pascal, de modo que, cuando se vuelvan a proporcionar las mismas entradas, la función busque el valor guardado en lugar de realizar más llamadas recursivas.
  2. Hay una fórmula directa para pascal que se usa mucho:
    \text{pascal}(n,r) = \frac{n!}{r!(n-r)!}

    Crea una versión de pascal que use la fórmula. Compara la eficiencia de esta versión con la versión recursiva y determina si cada versión se ejecuta en tiempo constante, tiempo lineal, tiempo cuadrático o tiempo exponencial.