performance - ventaja - recursividad vs
¿Por qué debería la recursión ser preferida sobre la iteración? (18)
La iteración es más eficiente que la recursión, ¿verdad?
No necesariamente. Esta concepción proviene de muchos lenguajes tipo C, donde llamar a una función, recursiva o no, tenía una gran sobrecarga y creaba una nueva pila para cada llamada.
Para muchos idiomas, este no es el caso, y la recursión es igual o más efectiva que una versión iterativa. En estos días, incluso algunos compiladores de C vuelven a escribir algunas construcciones recursivas en una versión iterativa, o reutilizan el marco de pila para una llamada recursiva de cola.
La iteración es más eficiente que la recursión, ¿verdad? Entonces, ¿por qué algunas personas opinan que la recursión es mejor (más elegante, según sus palabras) que la iteración? Realmente no veo por qué algunos lenguajes como Haskell no permiten la iteración y fomentan la recursión. ¿No es absurdo alentar algo que tiene un mal rendimiento (y eso también cuando hay una opción más efectiva, es decir, la recursión está disponible)? Por favor arroja algo de luz sobre esto. Gracias.
La iteración es más eficiente que la recursión, ¿verdad?
Sí.
Sin embargo, cuando tienes un problema que se adapta perfectamente a una estructura de datos recursiva, la mejor solución siempre es recursiva .
Si pretende resolver el problema con iteraciones , terminará reinventando la pila y creando un código más feo y desordenado, en comparación con la elegante versión recursiva del código.
Dicho esto, la iteración siempre será más rápida que la recursión . (en una arquitectura de Von Neumann), por lo que si usa recursividad siempre, incluso cuando un ciclo sea suficiente, pagará una penalización de rendimiento.
"La iteración es más eficiente que la recursión" es realmente específica del lenguaje y / o del compilador. El caso que me viene a la mente es cuando el compilador se desenrolla en bucle. Si ha implementado una solución recursiva en este caso, será bastante más lenta.
Aquí es donde vale la pena ser un científico (probar hipótesis) y conocer tus herramientas ...
Aquí hay información sobre los pros y los contras de la recursión y la iteración en c:
http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html
Sobre todo para mí La recursión a veces es más fácil de entender que la iteración.
Como otros han declarado, no hay nada intrínsecamente menos eficiente sobre la recursión. Hay algunos idiomas en los que será más lento, pero no es una regla universal.
Dicho esto, para mí la recursión es una herramienta que se usará cuando tenga sentido. Hay algunos algoritmos que están mejor representados como recursión (al igual que algunos son mejores a través de la iteración).
Caso en punto:
fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)
No puedo imaginar una solución iterativa que podría hacer que el intento sea más claro que eso.
Como un nivel bajo, ITERATION trata con el registro CX para contar bucles y, por supuesto, registros de datos. RECURSION no solo se ocupa de que también agrega referencias al puntero de la pila para mantener referencias de las llamadas anteriores y luego cómo volver.-
Mi profesor de la Universidad me dijo que cualquier cosa que hagas con la recursión se puede hacer con Iteraciones y viceversa, sin embargo, a veces es más simple hacerlo por recursión que por iteración (más elegante) pero a un nivel de rendimiento es mejor usar Iteraciones.-
Compararía la recursión con un explosivo: puedes alcanzar un gran resultado en poco tiempo. Pero si lo usa sin precauciones, el resultado podría ser desastroso.
Me impresionó mucho probar la complejidad de la recursión que calcula los números de Fibonacci here . La recursividad en ese caso tiene complejidad O ((3/2) ^ n) mientras que la iteración solo O (n). ¡El cálculo de n = 46 con la recursión escrita en c # toma medio minuto! Guau...
La recursión en mi humilde opinión debe usarse solo si la naturaleza de las entidades es adecuada para la recursión (árboles, sintáctico, ...) y nunca debido a la estética. El rendimiento y el consumo de recursos de cualquier código recursivo "divino" deben ser analizados.
Creo que ayudaría entender algo de lo que realmente se trata el rendimiento. Este enlace muestra cómo una aplicación perfectamente codificada tiene mucho espacio para la optimización, ¡ es decir, un factor de 43! Nada de esto tiene algo que ver con la iteración frente a la recursión.
Cuando una aplicación se ha ajustado hasta el momento , llega al punto en que los ciclos guardados por iteración frente a la recursión pueden realmente marcar la diferencia.
En Java, las soluciones recursivas generalmente superan a las no recursivas. En C, tiende a ser al revés. Creo que esto se aplica en general a los lenguajes compilados de forma adaptativa frente a los lenguajes compilados de antemano.
Editar: por "en general" me refiero a algo así como una división de 60/40. Es muy dependiente de cuán eficientemente maneja el lenguaje las llamadas a métodos. Creo que la compilación de JIT favorece la recursividad porque puede elegir cómo manejar la alineación y utilizar los datos de tiempo de ejecución en la optimización. Sin embargo, depende mucho del algoritmo y del compilador en cuestión. Java, en particular, sigue siendo más inteligente sobre el manejo de la recursividad.
Resultados cuantitativos del estudio con Java (enlace PDF) . Tenga en cuenta que estos algoritmos son en su mayoría de clasificación, y están utilizando una máquina virtual Java anterior (1.5.x si leo a la derecha). A veces obtienen una mejora en el rendimiento de 2: 1 o 4: 1 mediante el uso de la implementación recursiva, y rara vez la recursividad es significativamente más lenta. En mi experiencia personal, la diferencia no suele ser tan pronunciada, pero una mejora del 50% es común cuando uso la recursividad de manera sensata.
Haskell no permite la iteración porque la iteración involucra un estado mutable (el índice).
Intente implementar la búsqueda en profundidad recursiva e iterativamente y dígame cuál le dio más facilidad para hacerlo. O combinar tipo. Para muchos problemas, se trata de mantener explícitamente tu propia pila y dejar tus datos en la pila de funciones.
No puedo hablar con Haskell ya que nunca lo he usado, pero esto es para abordar la parte más general de la pregunta planteada en tu título.
La iteración es solo una forma especial de recursión.
La recursión es la implementación típica de la iteración. Es solo un nivel más bajo de abstracción (al menos en Python):
class iterator(object):
def __init__(self, max):
self.count = 0
self.max = max
def __iter__(self):
return self
# I believe this changes to __next__ in Python 3000
def next(self):
if self.count == self.max:
raise StopIteration
else:
self.count += 1
return self.count - 1
# At this level, iteration is the name of the game, but
# in the implementation, recursion is clearly what''s happening.
for i in iterator(50):
print(i)
La recursividad es una de esas cosas que parecen elegantes o eficientes en teoría, pero en la práctica generalmente es menos eficiente (a menos que el compilador o el recompilador dinámico) esté cambiando lo que hace el código. En general, cualquier cosa que provoque llamadas de subrutinas innecesarias será más lenta, especialmente cuando se empuja / hace saltar más de 1 argumento. Cualquier cosa que pueda hacer para eliminar los ciclos del procesador, es decir, las instrucciones que el procesador debe masticar, es un juego limpio. Los compiladores pueden hacer un trabajo bastante bueno en estos días en general, pero siempre es bueno saber cómo escribir código eficiente a mano.
Me resulta difícil razonar que uno es mejor que el otro todo el tiempo.
Estoy trabajando en una aplicación móvil que necesita hacer un trabajo de fondo en el sistema de archivos del usuario. Uno de los hilos de fondo necesita barrer todo el sistema de archivos de vez en cuando, para mantener los datos actualizados para el usuario. Así que, con el temor de , había escrito un algoritmo iterativo. Hoy escribí uno recursivo, para el mismo trabajo. Para mi sorpresa, el algoritmo iterativo es más rápido: recursivo -> 37s, iterativo -> 34s (trabajando sobre la misma estructura de archivos exacta).
Recursivo:
private long recursive(File rootFile, long counter) {
long duration = 0;
sendScanUpdateSignal(rootFile.getAbsolutePath());
if(rootFile.isDirectory()) {
File[] files = getChildren(rootFile, MUSIC_FILE_FILTER);
for(int i = 0; i < files.length; i++) {
duration += recursive(files[i], counter);
}
if(duration != 0) {
dhm.put(rootFile.getAbsolutePath(), duration);
updateDurationInUI(rootFile.getAbsolutePath(), duration);
}
}
else if(!rootFile.isDirectory() && checkExtension(rootFile.getAbsolutePath())) {
duration = getDuration(rootFile);
dhm.put(rootFile.getAbsolutePath(), getDuration(rootFile));
updateDurationInUI(rootFile.getAbsolutePath(), duration);
}
return counter + duration;
}
Iterativo: - búsqueda iterativa de profundidad profunda, con retroceso recursivo
private void traversal(File file) {
int pointer = 0;
File[] files;
boolean hadMusic = false;
long parentTimeCounter = 0;
while(file != null) {
sendScanUpdateSignal(file.getAbsolutePath());
try {
Thread.sleep(Constants.THREADS_SLEEP_CONSTANTS.TRAVERSAL);
} catch (InterruptedException e) {
e.printStackTrace();
}
files = getChildren(file, MUSIC_FILE_FILTER);
if(!file.isDirectory() && checkExtension(file.getAbsolutePath())) {
hadMusic = true;
long duration = getDuration(file);
parentTimeCounter = parentTimeCounter + duration;
dhm.put(file.getAbsolutePath(), duration);
updateDurationInUI(file.getAbsolutePath(), duration);
}
if(files != null && pointer < files.length) {
file = getChildren(file,MUSIC_FILE_FILTER)[pointer];
}
else if(files != null && pointer+1 < files.length) {
file = files[pointer+1];
pointer++;
}
else {
pointer=0;
file = getNextSybling(file, hadMusic, parentTimeCounter);
hadMusic = false;
parentTimeCounter = 0;
}
}
}
private File getNextSybling(File file, boolean hadMusic, long timeCounter) {
File result= null;
//se o file é /mnt, para
if(file.getAbsolutePath().compareTo(userSDBasePointer.getParentFile().getAbsolutePath()) == 0) {
return result;
}
File parent = file.getParentFile();
long parentDuration = 0;
if(hadMusic) {
if(dhm.containsKey(parent.getAbsolutePath())) {
long savedValue = dhm.get(parent.getAbsolutePath());
parentDuration = savedValue + timeCounter;
}
else {
parentDuration = timeCounter;
}
dhm.put(parent.getAbsolutePath(), parentDuration);
updateDurationInUI(parent.getAbsolutePath(), parentDuration);
}
//procura irmao seguinte
File[] syblings = getChildren(parent,MUSIC_FILE_FILTER);
for(int i = 0; i < syblings.length; i++) {
if(syblings[i].getAbsolutePath().compareTo(file.getAbsolutePath())==0) {
if(i+1 < syblings.length) {
result = syblings[i+1];
}
break;
}
}
//backtracking - adiciona pai, se tiver filhos musica
if(result == null) {
result = getNextSybling(parent, hadMusic, parentDuration);
}
return result;
}
Claro que el iterativo no es elegante, pero a pesar de que actualmente se implementa de manera ineficiente, es aún más rápido que el recursivo. Y tengo un mejor control sobre él, ya que no quiero que funcione a toda velocidad, y dejaré que el recolector de basura haga su trabajo con más frecuencia.
De todos modos, no daré por sentado que un método es mejor que el otro, y revisaré otros algoritmos que actualmente son recursivos. Pero al menos de los 2 algoritmos anteriores, el iterativo será el del producto final.
No creo que haya algo intrínsecamente menos eficaz en la recursión, al menos en lo abstracto. La recursión es una forma especial de iteración. Si un lenguaje está diseñado para admitir bien la recursión, es posible que funcione tan bien como la iteración.
En general, la recursividad hace que uno sea explícito sobre el estado que está presentando en la próxima iteración (son los parámetros). Esto puede facilitar que los procesadores de lenguaje paralelicen la ejecución. Al menos esa es una dirección que los diseñadores de idiomas están tratando de explotar.
Varias cosas:
- La iteración no es necesariamente más rápida
- La raíz de todo mal: fomentar algo simplemente porque puede ser moderadamente más rápido es prematuro; hay otras consideraciones
- La recursión a menudo comunica de manera mucho más sucinta y clara su intención
- Al omitir el estado mutable en general, los lenguajes de programación funcionales son más fáciles de razonar y depurar, y la recursividad es un ejemplo de esto.
- La recursividad requiere más memoria que iteración.
en ntfs UNC max path como es 32K
C: / A / B / X / C ... se pueden crear más de 16K carpetas ...
Pero ni siquiera puedes contar el número de carpetas con ningún método recursivo, tarde o temprano todos darán desbordamiento de pila.
Solo un buen código iterativo ligero debería usarse para escanear carpetas profesionalmente.
Lo crea o no, la mayoría de los mejores antivirus no pueden escanear la profundidad máxima de las carpetas de UNC.