Preguntas generales sobre la recursión

Question

Según tengo entendido, las buenas soluciones recursivas pueden hacer que los problemas complicados sean más fáciles. Pueden ser más eficientes en términos de tiempo o espacio.

Mi pregunta es: esto no es gratis, y la pila de llamadas será muy profunda. Se consumirá mucha memoria. ¿Estoy en lo cierto?

Answer 1

Es difícil delimitar con precisión las compensaciones relacionadas con la recursividad.

En un nivel matemáticamente abstracto, la recursión proporciona un marco potente para describir el comportamiento explícito de una función. Por ejemplo, podemos definir matemáticamente factorial como

x! = 1    if x == 0 
x! = x * (x - 1)! else 

O podríamos definir una función más compleja de forma recursiva, por ejemplo, cómo podemos calcular "N elegir K":

C(n, k) = 1        if k == 0 
C(n, k) = 0        if k < 0 or if n > k 
C(n, k) = C(n - 1, k) + C(n - 1, k - 1) else 

Cuando se utiliza la recursividad como una técnica de implementación, no hay garantía de que terminará usando más memoria o produciendo código que se ejecuta de manera más eficiente. A menudo, la recursividad usa más espacio debido a la memoria requerida para contener los marcos de la pila, pero en algunos idiomas esto no es un problema ya que el compilador puede intentar optimizar las llamadas a las funciones (ver, por ejemplo, eliminación de llamadas). En otros casos, la recursividad puede agotar enormes recursos hasta el punto en que el código recursivo no puede terminar en problemas simples.

En cuanto a cuestiones de eficiencia, a menudo el código recursivo es sustancialmente menos eficiente que el código iterativo. Las llamadas a funciones son costosas, y la traducción ingenua de la recursión al código conduce a la duplicación innecesaria del trabajo. Por ejemplo, la aplicación ingenua de Fibonacci

int Fibonacci(int n) { 
    if (n <= 1) return n; 
    return Fibonacci(n - 1) + Fibonacci(n - 2); 
} 

Es terriblemente ineficiente y es tan lento que nunca ha utilizado en la práctica. Aunque el código es más limpio, la ineficiencia borra cualquier beneficio potencial de la recursión.

En otros casos, sin embargo, la recursividad puede ser un increíble ahorro de tiempo.A modo de ejemplo, mergesort es un algoritmo de ordenación muy rápido definido por una hermosa recursividad:

Mergesort(array, low, high) { 
    if (low >= high - 1) return; 
    Mergesort(array, low, low + (high - low)/2); 
    Mergesort(array, low + (high - low)/2, high); 
    Merge(array, low, low + (high - low)/2, high); 
} 

Este código es extremadamente rápido y el código iterativo que corresponde probablemente sería más lento, más difícil de leer, y más difícil de entender.

Por lo tanto, en resumen, la recursividad no es una cura mágica ni una fuerza a evitar. Ayuda a iluminar la estructura de muchos problemas que de otra manera podrían parecer difíciles o casi imposibles. Si bien a menudo conduce a un código más claro, a menudo lo hace a expensas del tiempo y la memoria (aunque no necesariamente es automáticamente menos eficiente, sino que puede ser más eficiente en muchos casos). Definitivamente vale la pena estudiar para mejorar el pensamiento algorítmico general y las habilidades para resolver problemas, incluso si nunca escribes otra función recursiva en tu vida.

Espero que esto ayude!

Answer 2

Cons: 
It is hard (especially for inexperienced programmers) to think recursively 
There also exists the problem of stack overflow when using some forms of recursion (head 
recursion). 
It is usually less efficient because of having to push and pop recursions on and off the 
run-time stack, so it can be slower to run than simple iteration. 

¿Pero por qué nos molestamos en usar las recursiones?

Pros: 
It is easier to code a recursive solution once one is able to identify that solution. The 
recursive code is usually smaller, more concise, more elegant, and possibly even easier to 
understand, though that depends on one’s thinking style☺ 
There are some problems that are very difficult to solve without recursion. Those problems 
that require backtracking such as searching a maze for a path to an exit or tree based 
operations are best solved recursively. 

Answer 3

Prácticamente la pila de llamadas no será muy profunda. Tomemos por ejemplo un algoritmo de dividir y conquistar como el quicksort que divide el problema en dos partes. Con una pila de llamadas de profundidad 32 puede ordenar los elementos 4G, que probablemente ni siquiera encajarán en la memoria de una computadora promedio. El consumo de memoria no es realmente un problema, es una pila y es gratis siempre y cuando no te quedes sin él ... (y con 32 niveles tienes muchos datos para almacenar allí para cada nivel).

Puede reescribir prácticamente todos los procesos resursivos en iterativos si mantiene el estado en el montón en una estructura de pila, pero simplemente complica el código. El escenario principal donde puede obtener beneficios reales de la reescritura es cuando tiene un código recursivo de cola que no necesita mantener el estado para cada llamada recursiva. Tenga en cuenta que para algunos lenguajes (la mayoría de los lenguajes de programación funcionales y C/C++, tal vez Java también), un buen compilador puede hacer esto por usted.

Answer 4

Eso depende. Los problemas para los que la recursividad es más adecuada serán resistentes a este problema. Un ejemplo común sería Mergesort, en el que para ordenar una lista de N elementos habrá sobre log2 (N) marcos de pila. Entonces, si su límite de marco de pila es 200 y ha utilizado 50 para cuando llame a Mergesort, eso todavía es suficiente para clasificar entre 2^150 elementos sin un desbordamiento de pila. Además, Mergesort no crea mucha memoria para cada marco de pila, por lo que el uso total de la memoria para Mergesort nunca debe ser significativamente más del doble del tamaño de la lista original.

Además, algunos idiomas (el esquema es un buen ejemplo) usa tail-call elimination para que el código se pueda escribir elegantemente usando la recursión, pero luego optimizado o compilado en un bucle iterativo. Esta es una de las formas en que LISP, al ser un lenguaje funcional, aún puede competir con C y C++ en términos de velocidad de ejecución.

Hay otra técnica llamada Trampolining que se puede usar para realizar operaciones aparentemente recursivas sin producir una pila de llamadas profunda. Pero a menos que esté integrado en una biblioteca o incluso en una construcción a nivel de lenguaje, esta técnica tiene una ventaja menos clara en productividad (en mi opinión).

Entonces, si bien es difícil argumentar en contra de un viejo bucle for x in xrange(10) en muchas situaciones, la recursión sí tiene su lugar.

Answer 5

Es solo costoso si su recursividad no es repetitiva de cola y su lenguaje no es compatible con la recursividad de cola. Consulte el siguiente artículo de Wikipedia sobre las llamadas de cola para una discusión sobre el tema:

http://en.wikipedia.org/wiki/Tail_call

De lo contrario, puede hacer que el código mucho más fácil de leer y más fácil de probar.

Answer 6

Depende del problema.

Si el problema requiere recurrencia, como una caminata en el árbol en profundidad, la única manera de evitar la recursión es simularlo escribiendo su propia pila. Eso no salvará nada.

Si el problema no requiere recurrencia, como la función factor-ho-hum normal o de fibonacci, ¿cuál es el punto? No estás ganando nada usándolo.

Es una clase bastante pequeña de problemas donde incluso podría tener una opción razonable.