Introducción
La recursividad es un concepto fundamental en matemáticas y en computación. También la podemos conocer como una alternativa diferente para implementar estructuras de repetición en otras palabras ciclos. En los módulos se hacen llamadas recursivas que se puede usar en toda situación en la cual la solución pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas.
Para darle una idea concreta de lo que le estaremos presentando en este trabajo le daremos un pequeño ejemplo:
La Matrushka es una artesanía tradicional rusa. Es una muñeca de madera que contiene otra muñeca más pequeña dentro de sí. Esta muñeca, también contiene otra muñeca dentro. Y así, una dentro de otra.
OBJETIVOS DEL TRABAJO
¿Por qué escribir programas recursivos?
¿Cómo escribir una función en forma recursiva?
¿Cuándo usar la recursividad? o ¿Cuándo no usar la recursividad?
¿Cómo diferenciar la recursividad de la iteración?
Definición
La recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin.
La recursividad se considerar una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * …, incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial. La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.
Ámbito de Aplicación:
– Problemas cuya solución se puede hallar solucionando el mismo problema pero con un caso de menor tamaño.
Razones de uso:
– Problemas "casi" irresolubles con las estructuras iterativas.
– Soluciones elegantes.
– Soluciones más simples
Las claves para construir un programa recursivo son:
Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.
Ejemplo en forma grafica de la recursividad
Consideremos el cálculo del factorial para n = 4, enviado como parámetro valor desde otro subprograma o desde el programa principal:
n = 4 Llamada a Factorial(4) es n = 0; No
Factorial = 4 * Factorial(3)
n = 3 Llamada a Factorial(3) es n = 0; No
Factorial = 4 * 3 * Factorial(2)
n = 2 Llamada a Factorial(2) es n = 0; No
Factorial = 4 * 3 * 2 * Factorial(1)
n = 1 Llamada a Factorial(1) es n = 0; No
Factorial = 4 * 3 * 2 * 1 * Factorial(0)
n = 0 Llamada a Factorial(0) es n = 0; Si
Factorial = 4 * 3 * 2 * 1 * 1
Factorial = 24
No es recomendable declarar a la función factorial como int, ya que cuando n = 8, 8! = 40320, este valor supera ampliamente el rango de los enteros (32767).
Es mejor definirla de tipo long int o de tipo float.
La evaluación del factorial de 4 procede como se muestra en la gráfica siguiente.
Seguimiento del algoritmo recursivo Factorial (4!).
En el extremo izquierdo se muestra el proceso de sucesión de llamadas recursivas (proceso de ida) hasta que se evalúa que 0! es igual a 1, con lo que termina la recursión.
En el extremo derecho, se muestran los valores que cada llamada recursiva que los devuelve al invocador, hasta que se calcula y se devuelve el valor final.
Algoritmo recursivo
Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.
FUNCIÓN Factorial(n)
VAR resultado: Entero
SI (n<2) ENTONCES
resultado = 1;
SINO
resultado = n * Factorial(n-1);
FSI
RETORNA resultado;
FFUNCIÓN
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.
Programa Ejemplo
Conclusión
Se puede decir que la recursividad es una técnica de programación bastante útil y muy interesante de estudiar. A través de los ejemplos que el individuo pueda revisar, aprenderá con más rapidez y sencillez lo que es programar recursivamente e incluir esta técnica cuando se le presente un problema. La asignación de memoria, sea estática o dinámica, en realidad se tendrá que aplicar en cualquier programa al momento de su codificación; tomando en cuenta que cada programador tiene su estilo de programar. El ejemplo de las muñecas Matrushka es un problema clave que tienen que ver directamente con lo que es la recursividad.
Web grafía
Google Chrome. Recursividad.
http://www.lcc.uma.es/~lopez/modular/recursion/transp_recursion.pdf
Google Chrome. Eloy Pascal, Juan Navas. Recursividad. 11 de septiembre de 2003. 3 de junio de 2011.
http://www.monografias.com/trabajos14/recursividad/recursividad#PROPIE
Mozilla Firefox. Carlos Romero Shollande. Recursividad. Viernes 8 de abril de 2011. Domingo 5 de Junio de 2011. http://caromeroshlp.blogspot.com/2011/04/recursividad.html
Internet Explorer. Tuc Negre. Algoritmo Recursivo. Miércoles, 23 de marzo de 2011. Domingo, 5 de junio de 2011. http://es.wikipedia.org/wiki/Algoritmo_recursivo
Enviado por:
Pablo Turmero