¿CÓMO OPERA LA RECURSIVIDAD?
Al estar trabajando con recursividad, la memoria de la computadora hace uso de una pila de recursión, la cual se divide de manera lógica en 4 segmentos:
1.- Segmento de código: Parte de la memoria donde se guardan las instrucciones del programa en código máquina.
2.- Segmento de datos: Parte de la memoria destinada a almacenar las variables estáticas.
3.- Montículo: Parte de la memoria destinada a las variables dinámicas.
4.- Pila de programa: Parte destinada a las variables locales y parámetros de la función que está siendo ejecutada.
Al terminar la función, se libera la memoria asignada en la pila y se vuelve a la instrucción actual.
La recursión trabaja dividiendo un problema en subproblemas. Un programa llama a un método con uno o más parámetros que describen un problema. Si el método detecta que los valores no representan la forma más simple del problema, se llama a sí mismo con valores de parámetros modificados que describen un subproblema cercano a esa forma.
Esta actividad continúa hasta que el método detecta la forma más simple del problema, en cuyo caso el método simplemente retorna, posiblemente con un valor, si el tipo de retorno del método no es void.
La pila de llamadas a método empieza a desbobinarse como una llamada a método anidada para ayudar a completar una evaluación de expresión. En algún punto, la llamada el método original se completa, y posiblemente se devuelve un valor.
Recursión infinita
La iteración y la recursión pueden producirse infinitamente. Un bucle infinito ocurre si la prueba o test de continuación del bucle nunca se vuelve falsa.
Una recursión infinita ocurre si la etapa de recursión no reduce el problema en cada ocasión de modo que converja sobre el caso base o condición de la salida.
En realidad, la recursión infinita significa que cada llamada recursiva produce otra llamada recursiva y esta a su vez otra llamada recursiva, y así para siempre. En la práctica, dicha función se ejecutará hasta que la computadora agote la memoria disponible y se produzca una terminación anormal del programa.
Cuando no utilizar la recursividad
La solución recursiva de ciertos problemas simplifica mucho la estructura de los programas. Como contrapartida, en la mayoría de los lenguajes de programación las llamadas recursivas a procedimientos o funciones tienen un coste de tiempo mucho mayor que sus homólogos iterativos. Se puede, por lo tanto, afirma que la ejecución de un programa recursivo va a ser más lenta y menos eficiente que el programa iterativo que soluciona el mismo problema, aunque, a veces, la sencillez de la estructura recursiva justifica el mayor tiempo de ejecución.
Los procedimientos recursivos se pueden convertir en no recursivos mediante la introducción de una pila y así emular las llamadas recursivas. De esta manera se puede eliminar la recursión de aquellas partes de los programas que se ejecutan más frecuentemente.
|