Unidad II Recursividad

Unidad II Recursividad
2.1 Definición
Recursión es una técnica de programación en el cual un método puede llamarse a sí mismo.  La recursión es muy interesante y una técnica efectiva en programación ya que puede producir algoritmos cortos y eficientes.
 Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo).
 Si la invocación de un subprograma(función o subrutina) se produce desde el propio subprograma se dice que se trata de un subprograma recursivo.
 Un método recursivo es un método, directa o indirectamente, se hace una llamada a sí mismo.
 La recursión consiste en el uso de métodos recursivos.
 2.2 Procedimientos recursivos
Los procedimientos recursivos o recurrentes se pueden clasificar en dos formas distintas:
-      Recursividad directa o
-       Recursividad indirecta
 La recursividad directa se presenta cuando el método se manda llamar a sí mismo dentro de su propio cuerpo de instrucciones.
            public int Metodo(int n)
            {
                        :
                        n = Metodo(n-1);
}
La recursividad indirecta se manifiesta cundo un método llama a otro y dentro del segundo se manda llamar alprimero. O cuando existe la llamada a métodos de forma encadenada y al terminar el último método llamado, transfiere el control al anterior, hasta llegar al método que inicio la serie de llamadas.
public int Metodo1(int n)
            {
                        :
                        n = Metodo2(n-1);
            }
public int Metodo2(int n)
            {
                        :                        n = Metodo1(n-1);
            }
Analizando el concepto de recursividad y su clasificación,  puede indicar que es un procedimiento infinito, que solo se detendrá en el momento que se agote la memoria, generando un error de programación y la interrupción del mismo.
Pero esto no es así, ya que debe existir un elemento que indica el retorno de un resultado concreto y no el retorno de la llamada al métodorecursivo o recurrente.
Forma de generar la recursividad
Un problema clásico: El factorial de un número.
Todos conocemos que la definición matemática del factorial de un número n se obtiene de la siguiente forma:
n! = 1*2*3*.......*n ó n! = n*(n-1)*(n-2)*.....1
Por definición matemática, también sabemos que:
0! = 1
Con lo que tendríamos la siguiente definición de factorial:
 
n!
        1           
Si n=0
Caso Base

n*(n-1)
Otros casos
Parte Recursiva
 Un problema que puede resolverse de manera recursiva, debe tener por lo menos caso base y 1 parte recursiva, sino no hay recursión.
 Ahora, para implementarlo en un lenguaje de programación como Java, solo tenemos que traducir nuestros casos bases y partes recursivas:
 










 Funcionamiento del proceso
n
Llamado a factorial
44*factorial(3)
3
    3*factorial(2)
2
        2*factorial(1)    
1
           1*factorial(0)
0
                   1
En general el proceso es (4*factorial(3*factorial(2*factorial(1*factorial(0)))))
Realizar de manera recursiva la sumatoria de n números naturales de manera recursiva.
La sumatoria de n números se realiza de la siguiente forma:
n=10
1+2+3+4+5+6+7+8+9+10 = 10+9+8+7+6+5+4+3+2+1
 
De tal formaque podemos determinar que:
1                                 si n = 1           paso básico
n + (n-1)                     si n > 1           paso inductivo o proceso recursivo
//5+suma(4+suma(3+suma(2+suma(1))))
 
Imprimir de manera recursiva la serie de fibonnaci
La serie de fibonacci trabaja de la siguiente forma:
Paso 1: Si tenemos dos semillas formadas por s1=0 y s1=1
0 1
Paso 2. Se sumanpara obtener el resultado
0 1 1
Ahora la semilla 1 se queda con el valor de la semilla 2 y el resultado se asigna a la semilla 2 y se vuelve a realizar el paso 2.  De tal forma que la serie queda de la siguiente forma:
0 1 1 2 3 5 8 13 21 34 55 89 ………….
 
Fibonnacci de manera recursiva
 
Fibonacci(0,1,21)=1
Fibonacci(1,1,21)=2
Fibonacci(1,2,21)=3
Fibonacci(2,3,21)=5...