Pregunta Ejemplo de recursión que no se puede lograr con While Loop [cerrado]


¿Hay situaciones en las que la recursión es necesaria, o incluso muy preferible a un bucle while en javascript o C # (no importa cuál, el uso parece ser el mismo).

Hay un ejemplo factorial en MSDN (Quité las cosas irrelevantes):

function factorial(num)
{
    var tmp = num;
    while (num-- > 2) {
        tmp *= num;
    }
    return tmp;
}

vs

function factorial(num)
{
     return (num * factorial(num - 1));
}

En resumen, ¿hay alguna situación en la que el segundo ejemplo sea preferible al primer rendimiento sabio? ¿Alguna vez se puede lograr algo que el primer ejemplo no puede? ¿Entonces qué?


5
2017-08-17 14:29


origen


Respuestas:


Además, los algoritmos recursivos (o implementaciones) no son inherentemente   Más lento que los iterativos. De hecho, cada algoritmo recursivo puede ser   implementado por una implementación iterativa equivalente a costa de   tener que realizar un seguimiento de algunos valores intermedios / temporales usted mismo,   donde la versión recursiva automáticamente realiza un seguimiento de aquellos en el   función llamada pila. - Es el código recursivo más lento que el código no recursivo

En resumen, hay una forma de escribirlo iterativamente en lugar de un método recursivo. Luego surgen preguntas como los gastos generales, como en java o python, en comparación con los accesos directos que existen en C, donde la recursión de los gastos generales termina siendo un salto en la metodología.

En Javascript, la recursión no es final antes de ES2015, por lo que la recursión se vuelve extremadamente deficiente en costos a largo plazo. Tomado de Rendimiento: recursión vs. iteración en JavascriptSin embargo, después de esto, Javascript TIENE TER / TCO, por lo que resulta menos costoso invertir en recursión. En mi opinión, es una mezcla de preferencias personales entre los dos en JS. Si puede hacer que la funcionalidad recursiva y la apariencia del código sean limpias y rápidas, funcionará aproximadamente a la par con la versión iterativa, que puede ser bastante atroz de seguir e incluso depurar.

En C #, la recursión a menudo puede ser más lenta que una solución iterativa a costa de la legibilidad. Sin embargo, de nuevo se trata de preferencias personales. Con C # creando una sobrecarga y un nuevo marco de pila en cada "bucle / paso", por lo general no es tan eficaz. En otros idiomas, la recursión es tan poderosa como una solución iterativa.

Para muchos idiomas, este no es el caso, y la recursión es igual o   más performante que una versión iterativa

Ver: ¿Recursión preferida? para algunas preguntas y respuestas adicionales sobre por qué se prefiere en algunos lenguajes que no son Java, C #, lenguajes con deficiencias generales.


4
2017-08-17 14:48



Si la tarea puede resolver con recursion, puedes resolverlo con loops y viceversa. En la recursión, el alcance de su método crea el mismo alcance una y otra vez. Por lo tanto, si el tamaño de su método es 1KB en el 10 los pasos recuran su lógica pasará 10KB espacio.En los bucles el espacio gastado será solo 1KB.

Hay tareas que puede resolver fácilmente por recursión, pero será difícil con bucles. Uno de ellos es el Torres de Hanoi


2
2017-08-17 14:40



Estoy totalmente de acuerdo con las respuestas anteriores: la recursión es a menudo conveniente para el enfoque. Es genial reducir el problema a una verificación de finalización, más un paso de procesamiento simple si no se hace. Deje que el sistema operativo se encargue de su contabilidad.

Estoy agregando la nota de que hay algunas funciones que no están primitivo recursivo El más conocido (y primer descubierto) es el Función Ackermann. En términos prácticos, tú podría implementalo con bucles y tu propia pila, pero tu en serio en serio no quisiera

En términos aún más prácticos, es muy poco probable que alguna vez necesite implementar una función que sea no primitiva recursiva. La función Ackerman es de gran interés teórico, pero no es algo que tengamos en la vida cotidiana, incluso en el aprendizaje profundo o la computación de alto rendimiento.


1
2017-08-17 18:07



El punto crucial en tu pregunta es la función de pila. return (num * factorial(num - 1)); No está en posición de cola, es decir, la llamada recursiva. factorial(num - 1) No es la última acción de la función recursiva. La última acción es la multiplicación con num. Entonces tus factorial necesita la pila para funcionar. Cuando eliminas la pila con una versión recursiva de cola. factorial(acc * num, num - 1), necesitas imitar la pila con un argumento adicional, a saber: acc.

Los bucles en sí mismos no son tan expresivos como la recursión, debido a la falta de una pila. Eso significa que no puede implementar una versión de bucle que sea equivalente a su implementación recursiva sin cola. En realidad tu while Implementación es equivalente a la versión recursiva de cola. factorial. Cola recursiva significa que todas las llamadas recursivas comparten un marco de pila y, por lo tanto, se eliminan, ya no hay una pila. Tu tmp es solo acc - Imita la pila de funciones y acumula el resultado de las iteraciones. Intenta implementar factorial con tu while bucle pero sin una variable adicional como tmp. Es imposible.

Sin embargo, el problema con las soluciones recursivas sin cola es que pueden hacer explotar la pila, mientras que tmp Sólo se almacena en el montón.

Aquí está la solución recursiva completa de la cola:

function fact(acc, num) {
  return num > 1
   ? fact(acc * num, num - 1) // tail recursive case
   : acc; // base case
}

console.log(fact(1, 5));

Conclusión: 

¿Hay situaciones en las que la recursión es necesaria, o incluso fuertemente preferible a un bucle while?

No. Recursión de cola y bucles simples son equivalentes. La recursión sin cola y los bucles con su propia pila son casi equivalentes, excepto que una función recursiva sin cola almacena sus resultados intermedios en la pila de función y, por lo tanto, pueden ocurrir desbordamientos de pila. Los bucles con una pila propia lo almacenan en el montón y, por lo tanto, no tienen esta limitación.


1
2017-08-18 05:29