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.htmlInternet 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