Unidad 2 Recursividad

Instituto Tecnológico Superior de Felipe Carrillo Puerto

Ingeniería en Sistemas Computacionales

Estructura de Datos

Esaú López Gómez Docente: Aranda Cuevas, Niels Henryk

Lunes 29 de Septiembre del 2014

Recursividad

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.

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

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 al primero. 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);

   }

En general el proceso es (4*factorial(3*factorial(2*factorial(1*factorial(0)))))

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 forma que 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))))

Procedimiento Recursivo

n Llamado a factorial

4 4*factorial(3)

3     3*factorial(2)

2         2*factorial(1)    

1            1*factorial(0)

0                    1