Hay bastantes casos en los que una solución recursiva es peor que una iterativa. Incluso un lenguaje funcional puro como Haskell admite soluciones iterativas en forma de comprensión de listas.
Considere los siguientes ejemplos en C y un tono de medidas.
Factorial :
- Cómo calcular el orden de crecimiento para un fragmento de código dado
- ¿Cuál es la diferencia entre las estructuras de datos de programación C y las estructuras de datos de programación Java?
- ¿Es necesario aprender Java antes de comenzar el curso de Estructuras de datos y Algoritmos en el IIT en Delhi?
- ¿Por qué el método de ordenación Javascript organiza los números de una matriz en orden ascendente con [código] (a - b) [/ código] y descendente con [código] (b - a) [/ código]?
- Cómo convertirse en un maestro de algoritmos C y estructuras de datos
doble fact_recur (int n)
{
volver n> 1? n * fact_recur (n-1): 1;
}
vs.
doble fact_iter (int n)
{
int i;
doble resultado = 1;
para (i = 1; i <= n; ++ i)
resultado * = i;
resultado de retorno;
}
Ambas variantes se compilan con la optimización -O3 usando gcc. Esto fue tan rápido que fue difícil de medir. Estas funciones tuvieron que colocarse en un archivo C separado, sin optimización de todo el programa, para que el compilador no pueda eliminar todo el bucle:
recursiva: 280 nanosegundos. (Esto es con gcc 5.4 – más reciente es más lento).
iterativo: 180 nanosegundos.
Clang no es muy diferente a gcc.
La iterativa es un poco más rápida, pero la recursiva es mucho más legible. Entonces iría por la versión recursiva en este caso debido a la legibilidad.
Próximo.
Fibonacci
doble fib_recur (int n)
{
si (n <= 1)
volver n;
más
devuelve fib_recur (n-2) + fib_recur (n-1);
}
vs.
doble fib_iter (int n)
{
resultados dobles *;
doble resultado;
int i;
si (n <= 1)
volver n;
resultados = (doble *) malloc (tamaño de (doble) * (n + 1));
resultados [0] = 0.0;
resultados [1] = 1.0;
para (i = 2; i <= n; ++ i)
resultados [i] = resultados [i-1] + resultados [i-2];
resultado = resultados [n];
libre (resultados);
resultado de retorno;
}
Claramente, al menos para n pequeña, fib_iter debería ser más lento debido al uso de malloc. Así que vamos a medirlo.
Para n = 2:
iterativo: 41 nanosegundos
recursivo: 5.4 nanosegundos
Como era de esperar, el recursivo es mucho más rápido, debido a malloc. Así que vamos a deshacernos de malloc:
doble fib_iter2 (int n)
{
doble resultado = 1;
doble anterior = 0;
int i;
si (n <= 1)
volver n;
para (i = 2; i <= n; ++ i) {
doble siguiente = anterior + resultado;
prev = resultado;
resultado = siguiente;
}
resultado de retorno;
}
fib_iter2: 2.5 nanosegundos
Esto es dos veces más rápido que la versión recursiva. Todavía no estoy impresionado.
Probemos con n = 10.
Iterativo: 14 nanosegundos
Recursivo: 234 nanosegundos (mucho peor que iterativo)
Seamos audaces e intentemos con n = 30:
Iterativo: 39 nanosegundos (como se esperaba)
Recursivo: 3.6 milisegundos (¡eso es 100,000 veces más lento!)
¿Entonces qué está pasando? La versión recursiva es muy derrochadora. Se recalcula lo mismo una y otra vez. Por ejemplo, con fib (10), llama a fib (8) + fib (9). Fib (9), a su vez, llama a fib (8) nuevamente.
Su complejidad es exponencial, pero con una base de exponente pequeña, es por eso que no crece tan mal. Está alrededor de [matemáticas] O (1.6 ^ n) [/ matemáticas].
Las cosas no son tan malas para el recursivo de los fibonacci recursivos, ya que hay algunas soluciones:
Memoization donde la función recordará algunos de los últimos valores devueltos.
doble fib_mem (int n)
{
resultados dobles * estáticos = NULL;
tamaño int estático = 0;
si (n <= 1)
volver n;
if (n + 1> tamaño) {
si (resultados)
libre (resultados);
resultados = calloc (n * 2, sizeof (doble));
tamaño = n * 2;
}
if (resultados [n]! = 0.0)
devolver resultados [n];
resultados [n] = fib_mem (n-2) + fib_mem (n-1);
devolver resultados [n];
}
Esto es significativamente más complicado y no es la implementación más óptima.
recursiva repetida con memorización : 4.7 nanosegundos.
Aquí el punto de referencia llama al mismo fib_mem (30) repetidamente, y los 4,7 nanosegundos es el promedio. Esto es más rápido que la alternativa iterativa, porque tuvo que calcular el resultado solo una vez y simplemente recuperarlo en todas las llamadas posteriores de fib_mem (). La memorización del algoritmo iterativo tendrá el mismo efecto.
solo recursivo con memorización : 107 nanosegundos.
Esta ejecución borra los datos guardados antes de cada llamada. Esto muestra que una sola llamada es más del doble de lenta con la recursividad, lo que no es tan malo como sin la memorización.
Desafortunadamente, la recursividad con la memorización no es tan legible como la versión iterativa, por lo que tanto la legibilidad como los aspectos de velocidad son peores con la recursividad.
Experiencia del mundo real:
Una vez tuve que volver a implementar el bucle principal de un solucionador de restricciones. Básicamente es un DFS que repasa los posibles estados del solucionador, con algunas podas.
Después de implementar la solución iterativa y recursiva, decidí mantener la variante recursiva que era mucho más legible.
Un año después lamenté mi decisión. Hubo dos problemas:
- Algunos problemas de restricción triviales, que tenían miles de variables no relacionadas, darían como resultado una recursión DFS muy profunda. Me estaba quedando sin pila.
Solución fácil: use algunas opciones de enlazador para aumentar la pila. - Quería implementar un algoritmo de backjumping. Es decir, volver al nivel K en la pila. Esto es trivial con algoritmos iterativos, pero muy feo y propenso a errores con recursividad. El resultado final, el código terminó el doble de largo y el doble de feo.
Por supuesto, no puedo generalizar a partir de un mal caso, pero casi nunca vi ninguna ventaja en la recursividad en C o C ++. Con lenguajes funcionales puros, las cosas deberían ser diferentes porque están orientadas a la recursividad.
EDITAR:
Joe Zbiciak me recordó que C ++ está ejecutando un DFS recursivo en su nombre. La ejecución recursiva de destructores de C ++ es muy intuitiva, por un lado, pero a veces desborda la pila, por otro. Un caso trivial, que podría probar, es la destrucción de una lista vinculada:
#include
Nodo de estructura {
Nodo (int data_, std :: unique_ptr && next_)
: data (data_), next (std :: move (next_))
{}
datos int;
std :: unique_ptr siguiente;
};
Lista de clase {
público:
vacío push_back (datos int) {
root = std :: make_unique (datos, std :: move (root));
}
privado:
std :: unique_ptr raíz;
};
Esto se ve bien, hasta que construyas una lista realmente grande. Lo siguiente se bloquea al destruir lst.
int main ()
{
Lista lst;
para (int i = 0; i <100000; i ++)
lst.push_back (i);
}
En este caso particular, de una estructura profundamente anidada, podemos evitar la recurrencia definiendo un destructor especializado:
Nodo :: ~ Nodo () {
while (siguiente) {
auto old_next = std :: move (siguiente);
next = std :: move (old_next-> next);
}
}
Este destructor iterativo no está limitado por la profundidad de la lista.
Con un árbol binario desequilibrado , es un poco más complicado. Tener un std :: vector con nodos no controlados. En el bucle, pop_back () un nodo, empuja () sus hijos al vector y destruye el nodo. Pare cuando el vector esté vacío. Esto se parece a BFS, pero no del todo.
Es frustrante que incluso con destructores, la recursión generada automáticamente es peor que la iteración.
