¿Los programadores y los ingenieros de software usan la recursividad? ¿Es más rápido en otros lenguajes de programación?

SI. Todo el tiempo. Incluso en lenguajes sin TCO como Javascript y Python.

Porque escribes código en primer lugar para que otros humanos puedan entenderlo, y solo en segundo lugar para que la computadora lo ejecute. Y a la mente humana le resulta muy natural manejar la recursividad (al menos mi mente), por lo que el código termina siendo más fácil de entender y menos propenso a contener errores.

TL; DR por lo demás: comience con la codificación de una solución recursiva , porque lo ayudará a “pensar mejor” sobre el problema que está resolviendo y verá la solución más elegante, y refactorizará el código iterativo para garantizar la mejor seguridad y rendimiento en general estuches para código de producción. Verá que el código iterativo que escribe después de haber pensado en el problema de forma recursiva es mucho más limpio y comprensible, también más fácil de paralelizar en el mismo caso, si no comienza con la versión iterativa.

Razonamiento más detallado:

Si encontrar código recursivo termina mucho más breve y más fácil de entender que las alternativas iterativas. Mi cerebro “piensa recursivamente”, así que cuando traduzco mi proceso de pensamiento en código, termina siendo recursivo con muchos temporizadores.

Pero hay una trampa. CUALQUIER MOMENTO que use la recursión en un idioma sin TCO (pista: la mayoría de los idiomas que usaría en la producción), debe estar ABSOLUTAMENTE seguro de que: la profundidad máxima de recursión es menor que el número que dará como resultado un error de desbordamiento de pila (o lo que sea el equivalente se llama en su lenguaje de programación), o da como resultado la asignación de demasiada memoria. Si la profundidad de recursión depende de un parámetro externo pasado a una función, probablemente valga la pena verificar ese parámetro antes de ejecutar el código de la función principal y lanzar una excepción.

Pero si es un principiante que usa un lenguaje SIN TCO, y no está absolutamente seguro de nada de lo anterior, intente comenzar con una solución iterativa si el código no se pone demasiado feo (pista: cualquier tipo de código que funcione los árboles y los gráficos se pondrán feos muy rápidamente si intentas codificarlos de forma iterativa).

Y sí, cuando refactorice el rendimiento o la “seguridad” , volverá a escribir su código recursivo en iterativo, pero nuevamente, es más fácil razonar recursivamente al principio, por lo que su solución será mucho más elegante si comienza con la recursividad.

En cuanto a los detalles de su pregunta,

Una solución recursiva ingenua puede aumentar la complejidad del tiempo para ciertos problemas, pero hay formas de evitarlo. Tome el clásico enésimo problema del número de Fibonacci, por ejemplo. La solución iterativa se ejecuta en tiempo O (n), mientras que la solución recursiva ingenua (reproducida a continuación) toma tiempo O (2 ^ n).

fib (n):
si n <= 1: devuelve n
de lo contrario: devuelve fib (n-1) + fib (n-2)

La razón de esta gran discrepancia es que para que la solución recursiva calcule fib (n-1) necesita calcular fib (n-1-1), etc., hasta n = 1, y hace todo esto nuevamente para el término fib (n-2). No solo eso, sino que cada llamada recursiva hace que se bifurque nuevamente, exponencialmente. Por lo tanto, se están volviendo a hacer muchos cálculos, pero podemos evitar esos cálculos adicionales utilizando la memorización .

Memorización

simplemente significa guardar el valor de retorno de la función por cada entrada y devolver ese valor en lugar de rehacer el cálculo. (Esto solo funciona si la función siempre devuelve el mismo valor dada la misma entrada, que en nuestro caso es verdadera). Si memoriza la función fib, se ejecuta nuevamente en O (n):

memo = nuevo mapa
fib (n):
memoed = memo.get (n)
si se recuerda: volver memorado
más si n <= 1: devuelve n
más:
ret = fib (n-1) + fib (n-2)
memo.put (n, ret)
volver ret

(fib (n-1) se calcula hasta n = 1, luego, cuando se ejecuta fib (n-2), ese valor ya se ha calculado para que regrese instantáneamente, lo que resulta en invocaciones de O (n) de fib.)

Si se deja como está, este código ahora es más difícil de leer, pero su idioma puede tener alguna forma de memorizarlo para que no contamine su código. Parece que hay una forma en Java 8, pero debe implementarla usted mismo. Si está usando Clojure, simplemente puede usar la función de memorización incorporada (ejemplos incluidos). Apuesto a que su solución recursiva en la competencia de programación podría haberse beneficiado de la memorización.

Como nota al margen, la solución recursiva memorable todavía usa el espacio O (n) en comparación con el espacio O (1) utilizado por la solución iterativa, pero muchos lenguajes funcionales tienen una forma automática inteligente de evitar el crecimiento de la pila llamada Tail Call Optimization (TCO) .

Tail Call Optimization (TCO)

significa que, en algunos idiomas, si coloca una llamada a la función como la última instrucción que se ejecutará y devolverá, el compilador puede desechar el marco de la pila actual antes de llamar a la función. Puede hacer esto porque sabe que ya no necesita ninguna de las variables locales o valores intermedios, ya que solo está devolviendo el valor de retorno de la función que está a punto de llamar. Tendrá que buscar en Google si su compilador / lenguaje tiene TCO (fuera de mi cabeza, java, C # y Python no, pero algunos compiladores de C ++ sí, y Clojure si usa la construcción loop / recur).

En la mayoría de los problemas recursivos, la llamada recursiva termina naturalmente en la posición de cola, pero en nuestra solución de Fibonacci, desafortunadamente, este no es el caso (ya que tenemos la memorización y la adición). Sin embargo, así como todas las soluciones iterativas pueden escribirse recursivamente, también pueden reescribirse todas las soluciones recursivas para que la llamada recursiva esté en la posición final. Esto se logra agregando uno o más parámetros “acumuladores” a la función y pasando los valores intermedios que necesite a través de ellos (esto solo debería agregar una cantidad constante al uso de memoria). Después de hacer todo esto, su código puede volver a ser feo, desafortunadamente.

Con todo esto en mente, para responder finalmente a su pregunta,

Sí, uso la recursión profesionalmente, pero solo cuando es más fácil de leer que la iteración y no se acumula el desbordamiento. Usaré la recursividad al atravesar un árbol o gráfico, como al analizar un archivo JSON o XML, o al atravesar un sistema de archivos. Estos son casos simples que tienen una profundidad finita que la pila puede manejar, por lo que el uso de memoria no es un problema. En cuanto a la complejidad del tiempo, debería ser O (n), igual que la iteración. Y la solución recursiva sería mucho más fácil de leer especialmente para el análisis JSON o XML, ya que el contexto generalmente importa dentro de los elementos anidados, y este contexto puede encapsularse en funciones separadas que se llaman recursivamente.

Últimamente he estado usando Clojure y, afortunadamente, lenguajes funcionales como ese contienen varias construcciones que te ayudan a evitar la necesidad de escribir funciones recursivas o bucles imperativos en primer lugar.

Espero que esto ayude.

Si. Un rotundo sí que viene con sus advertencias.

Considere un caso de uso al representar una página creada en algo como Visual Basic y desea representar esta página de Visual Basic en HTML a través de algún procesamiento.

Si tuviéramos que vincularlo para la representación HTML, digamos a través de C ++, necesitaríamos estructuras de datos y algoritmos apropiados para indicar qué es cada objeto de Visual Basic y su posición en una página web.

Al mirar la imagen de arriba, sabemos que se ve como una tabla internamente, es decir, cada botón es parte de la tabla. Tomaré solo la cuadrícula 4 * 4 con los números y operadores para simplificar.

Si cada número y operador fuera un objeto, tendría que pasar esta colección de objetos a mi función render (object) para renderizar en la página web. Si observa de cerca, esta colección en sí misma es parte del objeto de otra colección { display, {Backspace, CE, C}, {1,2,3,4....9, /,+...,= }} . Ajá. Recursividad

void function render (collection * obj) {
if(obj ->prop == 1) { // where 1 = collection, 0 = simple entity
//you may need to position and style outer collection, like a table with border
for(int i=0; i< obj->length; i++)
render (obj->child[i] ); //now render the objects
}
else {
//do positioning logic.
}
}


Es mucho más fácil trabajar con la recursión, una vez que pueda comprender el flujo requerido para resolver el problema. Sin embargo, las recursiones son problemáticas cuando necesita trabajar con estructuras de datos complejas y datos que están en el montón. La gestión de la memoria se convierte en un dolor a veces en escenarios complejos.

Sí, en la aplicación correcta, * NADA * supera la recursividad, pero al mismo tiempo, ¡es una depuración!

Si está caminando por el directorio, seguro, puede hacerlo con una pila, pero eso es más difícil de depurar que una versión basada en pila. Dime … ¿es esto más fácil que una pila realmente loca y mantenida a mano?

Vea la respuesta de Marcas Neal a ¿Hay alguna diferencia entre implementar una estructura de datos de pila y usar la forma predeterminada de recursión (llamando a la función) en términos de complejidad de tiempo y espacio al resolver un problema como Fibonacci o, en ese sentido, cualquier otro problema en Java?

En general, dado que es muy difícil de depurar, debe evitar la recurrencia si hay una alternativa. La respuesta de Marcas Neal a ¿Son los algoritmos recursivos más difíciles de depurar?

Sí, los programadores y los ingenieros de software usan la recursividad. Incluso agregaría que, para algunos lenguajes funcionales (como Haskell y Erlang), no puede usar la recursión (o, en otras palabras, debe usar la recursividad). Estos lenguajes no tienen una estructura en bucle, por lo que la repetición solo se puede obtener mediante el uso de funciones recursivas.

Sin embargo, debe tener en cuenta que estos lenguajes también tienen buenas optimizaciones, lo que hace que algunas funciones recursivas sean tan eficientes como una estructura de bucle (ya que el compilador esencialmente transformará la llamada recursiva en un bucle a sus espaldas). Una optimización notable es la Optimización de llamadas de cola (TCO).

Dicho esto, Python no tiene estas optimizaciones y nunca las tendrá. Por lo tanto, es posible que desee mantenerse alejado de las funciones recursivas, a menos que sepa lo que está haciendo.