algorithm - recursivos - ¿Debería usar recursión o memoria para un algoritmo?
recursividad en programacion (14)
Depende de lo que estés buscando. la programación dinámica (memorización) es casi siempre más rápida. A menudo por MUCHO. (es decir, cúbico a cuadrado, o exponencial a poli), pero en mi experiencia, la recursión es más fácil de leer y depurar.
Por otra parte, muchas personas evitan la recidiva como la peste, por lo que no les resulta fácil leer ...
Además, (¿de tercera mano?), Creo que es más fácil encontrar la solución dinámica después de que he encontrado la recursiva, así que termino haciendo las dos cosas. Pero si ya tiene ambas soluciones, Dynamic puede ser su mejor opción.
No estoy seguro si he sido útil, pero ahí tienes. Como en muchas cosas de la elección del algoritmo, YMMV.
Si tengo la opción de utilizar recursión o memoria para resolver un problema, ¿qué debo usar? En otras palabras, si ambas son soluciones viables, ya que dan el resultado correcto y se pueden expresar razonablemente en el código que estoy usando, ¿cuándo usaré una sobre la otra?
En el caso habitual, se enfrenta a dos criterios que lo ayudan a tomar una decisión:
- Tiempo de ejecución
- Legibilidad
El código recursivo suele ser más lento pero mucho más legible (no siempre, pero con mayor frecuencia. Como se dijo, la recursividad de cola puede ayudar si su idioma lo admite; de lo contrario, no hay mucho que pueda hacer).
La versión iterativa de un problema recursivo suele ser más rápida en términos de tiempo de ejecución, pero el código es difícil de entender y, debido a eso, frágil.
Si ambas versiones tienen el mismo tiempo de ejecución y la misma legibilidad, no hay ninguna razón para elegir una sobre la otra. En este caso, debe verificar otras cosas: ¿Cambiará este código? ¿Qué hay de mantenimiento? ¿Te sientes cómodo con los algoritmos recursivos o te están dando pesadillas?
La recursividad tiene una penalización de rendimiento asociada con la creación de marcos de pila, la penalización de la memorización es el almacenamiento en caché de los resultados. Si el rendimiento es una preocupación, la única forma de saberlo será probar en la aplicación.
En mi opinión personal, elegiré el método más fácil de usar y entender primero, que en mi opinión es recurrencia. Hasta que demuestre la necesidad de memorizar.
La regla de oro para usar se basa en la cantidad de superposición que tienen los subproblemas. Si está calculando los números de Fibonacci (el ejemplo clásico de recursión) hay un gran recálculo innecesario si usa la recursión.
Por ejemplo, para calcular F (4), necesito saber F (3) y F (2), por lo que calculo F (3) calculando F (2) y F (1), y así sucesivamente. Si utilicé recursividad, solo calculé F (2) y la mayoría de F (n) dos veces. Si uso la memorización, puedo mirar el valor hacia arriba.
Si realiza una búsqueda binaria, no hay superposición entre subproblemas, por lo que la recursión está bien. La división de la matriz de entrada por la mitad en cada paso da como resultado dos matrices únicas, que representan dos subproblemas sin superposición. La memorización no sería un beneficio en casos como este.
No estoy seguro de poder decir sin conocer el problema. A menudo querrías usar la memorización con recursión. Aún así, es probable que la memorización sea significativamente más rápida que la recursión si puede usarla como una solución alternativa. Ambos tienen problemas de rendimiento, pero varían de forma diferente según la naturaleza del problema / tamaño de la entrada.
No son mutuamente exclusivos. Puedes usar ambos.
Personalmente, construiría primero la función recursiva base y luego agregaría la memoria como un paso de optimización.
Selecciono la memoria porque generalmente es posible acceder a más memoria de almacenamiento dinámico que la memoria de almacenamiento.
Es decir, si su algoritmo se ejecuta en una gran cantidad de datos, en la mayoría de los idiomas se quedará sin espacio de pila recurrente antes de que se agote el espacio en el montón de datos de ahorro.
Si su problema es recursivo, ¿qué otra opción tiene para recurrir?
Puede escribir su función recursiva de forma que produzca cortocircuitos mediante la memorización, para obtener la velocidad máxima para la segunda llamada.
La recursividad no necesita usar una cantidad significativa de espacio de pila si el problema puede resolverse utilizando técnicas de recursividad de cola. Como dije anteriormente, depende del problema.
La memorización es solo un método de almacenamiento en caché que suele utilizarse para optimizar la recursión. No puede reemplazar la recursión.
Creo que podría confundir la memorización (que es, como otros han señalado, una estrategia de optimización de algoritmos recursivos) con la programación dinámica (que simula una solución recursiva pero que en realidad no usa recursividad). Si esa fuera su pregunta, diría que dependerá de sus prioridades: alta eficiencia de tiempo de ejecución (programación dinámica) o alta legibilidad (memoria, ya que la solución recursiva del problema aún está presente en el código).
var memoizer = function (fund, memo) {
var shell = function (arg) {
if (typeof memo[arg] !== ''number'') {
memo[arg] = fund(shell, arg);
}
return memo[arg];
};
return shell;
};
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, [0, 1]);
usa ambos!
No estoy de acuerdo con la afirmación de Tomalak de que con un problema recursivo no tienes más remedio que recurrir.
El mejor ejemplo es la serie de Fibonacci mencionada anteriormente. En mi computadora, la versión recursiva de F (45) (F para Fibonacci) toma 15 segundos para las adiciones 2269806339, la versión iterativa toma 43 adiciones y se ejecuta en unos pocos microsegundos.
Otro ejemplo bien conocido es Towers of Hanoi. Después de su clase sobre el tema, puede parecer que la recursión es la única forma de resolverlo. Pero incluso aquí hay una solución iterativa, aunque no es tan obvia como la recursiva. Aun así, lo iterativo es más rápido, principalmente porque no se requieren costosas operaciones de pila.
En caso de que esté interesado en la versión no recursiva de Towers of Hamoi, aquí está el código fuente de Delphi:
procedure TForm1.TowersOfHanoi(Ndisks: Word);
var
I: LongWord;
begin
for I := 1 to (1 shl Ndisks) do
Memo1.Lines.Add(Format(''%4d: move from pole %d to pole %d'',
[I, (I and (I - 1)) mod 3, (I or (I - 1) + 1) mod 3]));
Memo1.Lines.Add(''done'')
end;
Combina ambos. Optimice su solución recursiva mediante la memorización. Para eso está destinada la memorización. Para usar el espacio de memoria para acelerar la recursión.