Recursividad



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 otransformaciones gobernadas por un conjunto de reglas no ambiguas.
Para darle una idea concreta de lo que le estoy 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?
















RECURSIVIDAD

1.2. Definición.


Primero debemos decir que la recursividad no esuna estructura de datos, sino que es una técnica de programación que nos permite que un bloque de instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas.
Este concepto será de gran utilidad para el capítulo de la estructura de datos tipo árbol.
La recursividad es un concepto difícil de entender en principio, pero luego de analizar diferentes problemas aparecen puntoscomunes.
En Java los métodos pueden llamarse a sí mismos. Si dentro de un método existe la llamada a sí mismo decimos que el método es recursivo.
Cuando un método se llama a sí mismo, se asigna espacio en la pila para las nuevas variables locales y parámetros.
Al volver de una llamada recursiva, se recuperan de la pila las variables locales y los parámetros antiguos y la ejecución se reanudaen el punto de la llamada al método.

Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado.

1.3. Elementos de la Recursión

1.3. 1. Axioma

Es un caso donde el problema puede resolverse sin tener quehacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.

1.3.2. Formula recursiva

Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.
Por ejemplo: El factorial de un número

factorial(0)   ->  1
factorial(1)   ->  1*factorial(0)
factorial(2)   -> 2*factorial(1)
factorial(3)   ->  3*factorial (2)
…               ->  …
factorial(N)   ->  3*factorial (N-1)

En la resolución de algoritmos recursivos es imprescindible encontrar estos dos elementos.
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 aFactorial(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....