Complejidad y funciones recursivas

> Tutorial de LeekScript

Advertencia: Este artículo es matemáticamente intensivo (al menos para este wiki). No lo use sin consejo médico.

Más en serio: aquí voy a tratar de hablar sobre la Optimización de las funciones recursivas (The_Recursion). Este artículo es más para personas interesadas en la programación funcional y la teoría de la programación.

No siempre es fácil, al escribir una función recursiva, saber cuántas llamadas haremos antes de llegar al resultado. O incluso si llegaremos al resultado, a veces. El tutorial sobre La_Récursivité da formas de optimizar las funciones recursivas, pero no estudia la complejidad o la corrección; Por lo tanto, ilustraré aquí con ejemplos algunos métodos para orientarse.

Esta lista de ejemplos no pretende ser exhaustiva, será necesario que cada uno de sus algoritmos examine con precisión las operaciones realizadas.

Luego depende de ti copiar estas ideas para tus algoritmos personales, y si encuentras otros ejemplos que vale la pena mencionar, ¡explícalos aquí!

Primeros ejemplos

Algunas funciones recursivas simples tienen una complejidad fácil de estudiar. Este es el caso del primer ejemplo del tutorial sobre recursividad:

función sumaN(n) { si (n === 0) { devuelve 0; } más { devuelve n + sumN(n - 1); } }

Aquí, es bastante simple: podemos ver fácilmente que si le damos un número entero n (¡positivo!) a esta función, sumará n a la suma de 0 a n-1, que calcula llamándose a sí misma-igual. Así que vamos a hacer n + (n-1 + ... + (0)...), que hace n sumas y n llamadas a funciones, es decir, una complejidad de O( n).

Sin embargo, si damos un entero negativo como entrada, esta función provocará un desbordamiento de la pila: sumará números negativos sin llegar nunca a 0. De forma similar, si damos un número no entero, nunca llegaremos a 0 restando 1 varias veces. . Así que presta atención a la '''corrección''' de tus funciones recursivas: si no has previsto todos los casos o si los usas con una entrada que no se corresponde con lo que tenías en mente al codificarla, podrías tener sorpresas desagradables.

El tutorial de optimización da un ejemplo de una función de complejidad O(2^n):

función getAllCombos(list_items){ var nb_items = contar (list_items);

si (nb_elementos == 1) { volver [[], list_items]; }

var sub_list = subArray(list_items, 1, nb_items - 1); var parcial_combos_list = getAllCombos(sub_list); // llamada recursiva var m = cuenta(lista_combos_parcial);

//Luego duplicamos la lista de combos: mantenemos los que teníamos, y agregamos los mismos con el primer elemento de liste_items para(var i=0; i P(n) = 2*P(n-1). Como también tenemos P(1) = 2, obtenemos la fórmula P(n) = 2 * ... * 2 = 2^n, de ahí el (en menos) complejidad exponencial. Entonces podemos mostrar que esta función tiene una complejidad exponencial (y no mayor): cada llamada a la función crea una matriz de tamaño n-1 con subArray (cost: O(n )), luego hace m push con m del tamaño de la matriz combinada parcial, es decir, 2^(n-1) (costo: K * 2^(n-1) con K el push cost), lo que aplasta el costo del subArray y, por lo tanto, conduce a una complejidad determinada por el número P(n) de inserciones realizadas.

Es esta idea la que desarrollaré aquí: obtener una fórmula de recurrencia e intentar deducir una fórmula para aumentar el número de llamadas, para finalmente deducir la complejidad estudiando qué hace la función además de sus llamadas recursivas. Ya no hablaré tanto sobre la corrección (excepto al final), pero ten en cuenta la noción...

En lo que sigue, C(n) denotará el costo de la función estudiada.

Recurrencias simples: C(n) = f(C(n-1))

La palabra "simple" aquí no significa que la complexi