Si consideramos la función recursiva en C/C++, ¿son útiles de alguna manera? ¿Dónde exactamente se usan principalmente? ¿Hay alguna ventaja en términos de memoria mediante el uso de funciones recursivas?Funciones recursivas en C/C++
Editar: ¿la recursión es mejor o usa un ciclo while?
Las funciones recursivas se utilizan principalmente para facilitar el diseño de algoritmos. Por ejemplo, necesitas atravesar un árbol de directorios de forma recursiva: su profundidad es limitada, por lo que es muy probable que nunca enfrentes nada como recursividad demasiado profunda y el consecuente desbordamiento de pila, pero escribir un recorrido de árbol recursivamente es mucho más fácil, luego hacer lo mismo de manera iterativa.
En la mayoría de los casos, las funciones recursivas no ahorran memoria en comparación con las soluciones iterativas. Peor aún, consumen memoria de pila, que es relativamente escasa.
-1: Defina "relativamente escaso". En las computadoras actuales, la pila es relativamente ilimitada; solo la memoria virtual establece los límites. Stack tiene la ventaja de no fragmentarse como la memoria asignada en el montón: la fragmentación es una gran amenaza para la gestión de la memoria, ya que también puede quedarse sin memoria sin utilizar realmente toda la memoria. – Juergen
Para la ventaja de la memoria de pila, vea también mi respuesta. – Juergen
La memoria de la pila es escasa a medida que se le asigna la cantidad establecida de espacio de direcciones. La gestión de memoria moderna puede manejar fácilmente una pila en crecimiento, pero cuando el espacio de direcciones está lleno no queda lugar para crecer y la pila se segmenta. Este problema empeora cuando los hilos se involucran, ya que el espacio de direcciones de la pila suele ser incluso más limitado que el principal. Esto ya no puede ser un problema en los espacios de direcciones de 64 bits, ya que la (s) pila (s) se pueden asignar a secciones increíblemente grandes del espacio de direcciones sin limitar las secciones de instrucciones o de pila. –
tienen muchos usos y algunas cosas se vuelven muy difíciles o imposibles sin ellos. iterando árboles por ejemplo.
Al utilizar recursividad, puede almacenar datos en la pila (efectivamente, en los contextos de llamada de todas las funciones sobre la instancia actual) que tendría que almacenar en el montón con asignación dinámica si estuviera tratando de hacer lo mismo con un lazo while. Piense en la mayoría de los algoritmos de división y conquista donde hay dos cosas que hacer en cada llamada (es decir, una de las llamadas no es recursiva).
Y en lo que respecta al interesante comentario/incuestionado de Tom, esta ventaja de las funciones recursivas es tal vez particularmente notable en C, donde la gestión de la memoria dinámica es tan básica. Pero eso no significa que sea muy específico para C.
También puede almacenar datos en la pila en un bucle 'while'. Simplemente declare una matriz de elementos y úselos como la pila. –
@Paul Eso es implementar la propia pila. Obliga al programador a calcular la profundidad máxima de la pila de su algoritmo para que pueda asignar una matriz del tamaño correcto. –
Sí, está implementando la propia pila (estructura de datos) utilizando la pila de programas (para variables locales). El programador debe tener en cuenta la profundidad máxima de pila de todos modos, ya que la pila para llamadas a funciones recursivas tampoco es infinita. No creo que la asignación de memoria dinámica que describes sea más fácil que implementar la propia pila.La recursividad es más fácil que ambas, que es una razón para preferirla en algunas situaciones. –
Hay dos razones que veo para el uso de la recursividad:
Maneje la recursión con cuidado, ya que siempre existe el peligro de recursión infinita.
Como también existe el peligro de bucles infinitos ... Por supuesto, las recurrencias infinitas son más temidas, ya que las situaciones pueden ser más complicadas y un desbordamiento de la pila sigue (mientras que algunos bucles infinitos no desbordan nada, siempre que no asignar más y más memoria), pero los bucles infinitos también deben evitarse como la recursión infinita. – Juergen
Los bucles infinitos son mucho más fáciles de entender que la recursión infinita. La recursión compleja con múltiples funciones involucradas es muy difícil de depurar adecuadamente. – Thorsten79
Dynamic programming es un área clave donde la recursividad es crucial, aunque va más allá (recordar sub-respuestas puede dar drásticas mejoras de rendimiento). Los algoritmos son donde se usa normalmente la recursividad, en lugar de la codificación típica del día a día. Es más un concepto de computadora ciencia que uno de programación.
Las funciones recursivas hacen que sea más fácil codificar las soluciones que tienen un recurrence relation.
Por ejemplo, la función factorial tiene una relación de recurrencia:
factorial(0) = 1
factorial(n) = n * factorial(n-1)
continuación he implementado factorial utilizando recursividad y los bucles.
La relación recursiva y la relación recursiva definidas anteriormente tienen un aspecto similar y es , por lo tanto, es más fácil de leer.
recursiva:
double factorial (int n)
{
return (n ? n * factorial (n-1) : 1);
}
Looping:
double factorial (int n)
{
double result = 1;
while (n > 1)
{
result = result * n;
n--;
}
return result;
}
Una cosa más:
La versión recursiva del factorial incluye una llamada de cola a sí mismo y puede ser llamada final optimizado. Esto lleva la complejidad del espacio de factorial recursivo a la complejidad espacial del factorial iterativo.
"La versión recursiva de factorial incluye una llamada final a sí mismo". No, no es así. La última operación no es la llamada recursiva, sino la multiplicación de n con el resultado de la llamada recursiva. La versión recursiva de cola de factorial se suele definir utilizando una función auxiliar que toma un acumulador como segundo argumento. – sepp2k
Deliberadamente haces que tu versión recursiva sea más corta, usando una declaración abreviada if/else. Expandir eso y mejorar su versión de bucle rinde funciones muy similares. Este no es un buen ejemplo de que la recursividad sea mejor. –
Implemente QuickSort con y sin usar recursividad, entonces puede saber usted mismo si es útil o no.
La recursividad definitivamente tiene ventajas en los problemas de naturaleza recursiva. Otros carteles nombraron algunos de ellos.
Usar la capacidad de C para recursividad definitivamente tiene ventajas en la administración de la memoria. Cuando intenta evitar la recursión, la mayoría de las veces se usa una pila propia u otro tipo de datos dinámicos para resolver el problema. Esto implica la gestión de memoria dinámica en C/C++. ¡La gestión dinámica de la memoria es costosa y propensa a errores!
No se puede superar la pila
Por otro lado, cuando sólo tiene que utilizar la recursividad pila y su uso con las variables locales - la gestión de memoria es sólo simple y la pila es la mayoría del tiempo más eficiente en el tiempo que toda la administración de memoria que puede hacer usted mismo o con administración simple de memoria C/C++. La razón es que la pila del sistema es una estructura de datos simple y conveniente con poca sobrecarga y se implementa utilizando operaciones especiales del procesador que están optimizadas para este trabajo. Créanme, no se puede superar eso, ¡ya que los compiladores, los sistemas operativos y los procesadores están optimizados para manipulaciones de pila durante décadas!
PD: Además, la pila no se fragmenta, como la memoria de pila hace fácilmente. De esta manera, también es posible ahorrar memoria utilizando la pila/recursión.
-1. Asumir que la pila puede crecer indefinidamente es solo una receta para segfaults. La pila tiene algunas ventajas definidas, sí, pero confiar en almacenar grandes cantidades de datos es simplemente una mala idea. – jalf
Como en su otro comentario: ¡Agregue algunas pruebas por favor! La pila es (de acuerdo con mi información) de la misma manera limitada que el montón. Por lo tanto, cuando abogas por utilizar el montón, te metes en problemas diferentes (¡ya que el montón también es limitado!). Nuevamente: ¡NO DÉ A MALOS MALOS MARCOS SIN PRUEBA! – Juergen
Estoy de acuerdo con usted. Dada la elección, elige la pila. Sin embargo, jalf es correcto. Al almacenar grandes cantidades de datos, o al usar un algoritmo con recursión muy profunda, la pila puede quedarse sin espacio rápidamente. En Linux, de forma predeterminada, la pila solo puede crecer hasta un máximo de 2 MB. Windows tiene un límite similar (más pequeño). Ambos permiten a los usuarios especificar un tamaño de pila más grande, pero ninguno tiene una opción para el crecimiento ilimitado de la pila. –
A menudo encuentro algoritmos recursivos más fáciles de entender porque implican un estado menos mutable. Considere el algoritmo para determinar el máximo divisor común de dos números.
unsigned greatest_common_divisor_iter(unsigned x, unsigned y)
{
while (y != 0)
{
unsigned temp = x % y;
x = y;
y = temp;
}
return x;
}
unsigned greatest_common_divisor(unsigned x, unsigned y)
{
return y == 0 ? x : greatest_common_divisor(y, x % y);
}
Hay demasiados cambios de nombre en la versión iterativa para mi gusto. En la versión recursiva, todo es inmutable, por lo que incluso podría hacer xy y const si quisiera.
Una cosa que vale la pena mencionar es que en la mayoría de los lenguajes funcionales (Scheme por ejemplo), puede aprovechar las optimizaciones de cola y así puede usar funciones recursivas sin aumentar la cantidad de memoria en su pila.
Básicamente, las llamadas de cola recursivas complejas se pueden ejecutar sin problemas en Scheme, mientras que en C/C++ las mismas crearán un desbordamiento de pila.
Fuera de interés, ¿la respuesta a esta pregunta es diferente si tenemos en cuenta otros idiomas que permiten la recursión? –
Por supuesto. En lenguajes funcionales como Haskell, la recursividad se usa casi en cada lugar_. Sin embargo, esto se puede generalizar a más que solo C/C++, a menos que esté muy especialmente interesado en cómo se maneja la memoria en C/C++. –
Muchos engañados incluyen http: // stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion –