Introducción.
Normalmente, una solución recursiva es menos eficiente en términos de tiempo de computadora que una solución iterativa debido al tiempo adicional de llamada a procedimientos.
En muchos casos, la recursion permite especificar una solución mas simple y natural para resolver un problema que en otro caso seria difícil. Por esta razón la recursion (recursividad) es una herramienta muy potente para la resolución de problemas de programación.
Un objeto recursivo es aquel que forma parte de si mismo. Esta idea puede servir de ayuda para la definición de conceptos matematicos. Asi, la definición del conjunto de los numeros naturles es aque conjunto en el que se cumplen las siguientes caracteristicas:
• 0 es un numero natural.
• El siguiente numero de un numero natural es otro numero natural.
Mediante una definición finita hemos representado un conjunto infinito.
El concepto de la recursividad es muy importante en programación. La recursividad es una herramienta muy eficaz para resolver diversos tipos de problemas existen muchos algoritmos que se describiran mejor en terminos recursivos.
Algoritmos recursivos
Un método común de simplificación consiste en dividir un problema en subproblemas del mismo tipo. Como técnica de programación, esto se denomina división y conquista, y constituye la llave para el desarrollo de muchos algoritmos importantes, así como un elemento fundamental del paradigma de programación dinámica.
Prácticamente todas las lenguajes de programación usadas hoy día permiten la especificação directa de funciones y procedimientos recursivos. Cuando una función es invocada, el ordenador (en la mayoría de los lenguajes sobre la mayor parte de las arquiteturas basadas en pilas) o la implementación del lenguaje registra las varias instancias de una función (en muchas arquiteturas, se usa una pila de llamada, aunque otros métodos puedan ser usados). Recíprocamente, toda función recursiva puede ser transformada en una función iterativa usando una pila.
Toda función que pueda ser producida por un ordenador puede ser escrita como función recursiva sin el uso de iteração; recíprocamente, cualquier función recursiva puede ser descrita a través de iterações sucesivas.
Dentro de la teoría de la recursión, se tiene que existen diferentes tipos de recursión:
Recursión directa. Cuando el código F tiene una sentencia que involucra a F.
Recursión indirecta o cruzada.- Cuando la función F involucra una función G que invoca a la ves una función H, y así sucesivamente, hasta que se involucra la función F. Por ejemplo el algoritmo de Par o impar.
int par (int n)
{
if (n==0) return n+1;
return impar(n-1);
int impar(int n)
if (n==0) return 0;
return par(n-1);
}
A continuación se expone otro ejemplo de programa que utiliza recursión indirecta, y nos dice si un número es par o impar. Cabe mencionar que existen otros métodos mucho más sencillos para determinar la solución a este problema, basta con determinar el resto de la división entre dos. Por ejemplo: si hacemos par(2) devuelve 1 (cierto). Si hacemos impar(4) devuelve 0 (falso).
int par(int n);
int impar(int n);
int par(int n)
{ if (n == 0) return 1;
return impar(n-1);
}
int impar(int n)
{
if (n == 0) return 0;
return par(n-1);
}
Recursión simple.- Aquella en cuya función solo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iteractivos.
Recursión múltiple.- Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de transformar a iteractiva. Poe ejemplo el algoritmo de Fibonacci.
int fibo(int n)
{
if (n<=1) return 1
return fibo(n-1) + fibo(n-2)
}
Recursión anidada.- En algunos de los argumentos de la llamada hay una nueva llamada a sí misma. Por
ejemplo la función de Ackerman:
int Ack(int m, int n)
{
if (m==0) return n+1
if (n=00) return Ack(n-1, 1)
return Ack(m-1, Ack(m, n-1));
}
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:
Segmento de código.- Parte de la memoria donde se guardan las instrucciones del programa en código máquina.
Segmento de datos.- Parte de la memoria destinada a almacenar las variables estáticas.
Montículo.- Parte de la memoria destinada a las variables dinámicas.
Pila de programa.- parte destinada a las variables locales y parámetros de la función que está siendo ejecutada.
Funciones mutuamente recursivas
Cuando se trabaja llamados a la ejecución de las funciones, se provocan las siguientes operaciones:
1.- Reservar espacio en la pila para los parámetros de la función y sus variables locales.
2.- Guardar en la pila la dirección de la línea de código desde donde se ha llamado a la función.
3.- Almacenar los parámetros de la función y sus valores de pila.
4.- Al terminar la función, se libera la memoria asignada en la pila y se vuelve a la instrucción actual.
Pero cuando se trabaja con funciones recursivas, se provoca además lo siguiente:
1.- La función se ejecutará normalmente hasta la llamada a sí misma. En ese momento se crean en la pila nuevos parámetros y variables locales.
2.- El nuevo ejemplar de función comienza a ejecutarse.
3.- Se crean más copias hasta llegar a la primera llamada (ultima en cerrarse).
La ciencia de la computación hace tiempo que descubrió que se puede reemplazar a un método que utiliza un bucle para realizar un cálculo con un método que se llame repetidamente a sí mismo para realizar el mismo cálculo. El hecho de que un método se llame repetidamente a sí mismo se conoce como recursion.
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, larecursió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.
El flujo de control de una función recursiva requiere de tres condiciones para una terminación normal.
CUANDO NO UTILIZAR RECURSIVIDAD.
La solucion recursiva de ciertos problemas simplifica mucho la estructura de los programas. Como contrapartida, en la mayoria de los lenguajes de programación las llamadas recursivas a procedimientos o funciones tienen un coste de tiempo mucho mayor que sus homologos iterativos. Se puede, por lo tanto, afrimar que la ejecución de un programa recursivo va a ser mas lenta y menos eficiente que el programa iterativo que soluciona el mismo problema, aunque, a veces, la sencilles de la estructura recursiva justifica el mayor tiempo de ejecucion.
Los procedimientos recursivos se pueden convertir en no recursivos mediante la introducción de una pila y asi emular las llamadas recursivas. De esta manera se puede eliminar la recursion de aquellas partes de los programas que se ejecutan mas frecuentemente.
Bibliografias:
http://www.programacionfacil.com/estructura_datos_csharp:mecanica_de_recursion
http://es.wikilingue.com/pt/Recursividade_(ciencia_de_la_computaci%C3%B3n)
+5 lab
ResponderEliminar