Inicio > Programacion, python > Recursividad

Recursividad

Siguiendo con el estudio para el parcial de Diseño e Implementación de Estructuras de Datos, vamos a ver la Recursión.
Se dice que un proceso es recursivo si forma parte de sí mismo, es decir, que se define en función de sí mismo. La recursión aparece en la vida diaria, en problemas matemáticos, en estructuras de datos y en muchos otros problemas. Es un proceso extremadamente potente, por lo que hay que saber cuándo y cómo aplicarla.

Un método recursivo es un método que, directa o indirectamente, se hace una llamada a sí mismo

En las aplicaciones prácticas, antes de poner en marcha un proceso recursivo es necesario demostrar que el nivel máximo de recursión (que es es el número de veces que se va a llamar a sí mismo), es no solo finito, sino realmente pequeño. La razón es que necesitaremos una cierta cantidad de memoria para almacenar el estado del proceso cada vez que se abandona temporalmente, debido a una llamada para ejecurtar un proceso de sí mismo. El estado de cálculo en curso hay que almacenarlo para recuperarlo cuando se acabe la nueva ejecución del proceso y haya que reanudar la antigua.
Por esta razón a la existen 4 reglas fundamentales de la recursión, que tenemos que tener en cuenta a la hora de realizar nuestro algoritmo.

  1. Caso Base: se debe tener siempre, al menos un caso base que pueda resolverse sin recursión.
  2. Progreso: cualquiera llamada recursiva debe progresar hacia un caso base.
  3. Puede creerlo: asuma siempre que toda llamada recursiva interna funciona correctamente.
  4. Interes compuesto: nunca duplique el trabajo resolviendo la misma instancia de un problema, en llamadas recursivas separadas.

Tipos de recursión según su complejidad

  1. Resursión lineal: Un método recursivo es lineal, si como máximo tiene una llamada recursiva por rama del condicional, de manera que la cantidad de llamadas recursivas puede calcularse como una función lineal que dependerá de la velocidad con la cual progresa hacia el caso base. Ésta a su vez la subdividimos en:
    1. Resursión por la cola: es cuando la llamada recursiva se hace al final del método, no quedan operaciones pendientes sobre los datos, de manera que no hace falta representar con una pila las variables de cada llamada, y el método recursivo lo podriamos transformar tranquilamente en un bucle iterativo.
    2. Veamos el ejemplo del :Máximo común divisor entre a y b


      def mcd( a, b):
      if( b==0):
      return a
      else:
      return mcd( b, a%b)

    3. Recursión no por la cola: es cuando después de ejecutar todas la llamadas recursivas el método debe realizar una operación pendiente para completar le proceso.
    4. Veamos el ejemplo: Obtener el factorial de un número


      def factorial(n):
      if( n==1):
      return 1
      else:
      return n * factorial(n-1)

      Como vemos luego de ejecutar las llamadas recursivas debemos realizar la operacion “*”.

  2. Recursión no lineal: Un método recursivo es no lineal, si hay más de una llamada recursiva por rama del condicional.
    1. Recursión en cascada: es cuando en cada rama hay mas de una llamada a la función recursiva,su complejidad en término de llamadas recursivas será una función exponencial de la profundidad del árbol de las llamadas.
    2. Veamos el ejemplo: Obtener el n-ésimo valor de la serie de Fibonacci


      def fibonacci(n):
      if( n<=1):
      return 1
      else:
      return fibonacci(n-1) + fibonacci(n-2)

    3. Recursión anidada: es cuando alguna llamada recursiva recibe como parámetro a una llamada recursiva, su complejidad en término de llamadas recursivas resultará mucho más dificil de calcular.
    4. Veamos el ejemplo: Función de Ackermann


      def Ackerman(m, n):
      if (m == 0):
      return n+1
      elif (m > 0 and n == 0):
      return ackermann(m-1, 1)
      elif (m > 0 and n > 0):
      return ackermann(m-1, ackermann(m, n-1))

  3. Recursión mutua: se da cuando dos funciones son recurrentes entre sí.
  4. Veamos el ejemplo: decir si es par o impar el parámetro.


    def impar(n):
    if (n==0):
    return false;
    else
    return par(n-1)

    def par(n):
    if (n==0):
    return true
    else:
    return impar(n-1)

Me parece que los aburrí con tanta teoría🙂... Falta solo un poco. Que mas podemos comentar de la Recusión?, como la implementamos?. Existen distintas estrategias, trataré de explicar un poco de cada una:

  1. Divide y vencerás: dijo Napoléon Bonaparte🙂
    Estos algoritmos constan de dos partes:

    1. Dividir: se resuleven recursivamente problemas más pequeños (exepto los del caso base).
    2. Vencer: la solución al problema original se consigue a partir de las soluciones a los subproblemas.
  2. Estos algoritmos son generalmente muy eficientes y tienen menos llamadas recursivas. Por lo general el Orden de éstos algoritmos es del O(N log N).

  3. Programación dinámica: es la técnica que evita la explosión recursiva guardando respuestas en una tabla. Esta estrategia de Agarra todo lo que puedas es la fuente el nombre de esta clase de algoritmos. Resulta agradable que un problema se pueda resolver usando un algoritmo devorador, ya que entonces el algoritmo se suele acercar bastante a nuestra intuición y además el código producido resulta comprensible. Pero como todo no es color de rosas, no siempre funcionan bien.
    El truco está en guardar las soluciones de los subproblemas en un vector.
  4. Algoritmos de vuelta atrás: usan la recursión para probar sistemáticamente todas las posibilidades

Para terminar un buen ejemplo: ¿Qué es la Recursividad?

Categorías:Programacion, python
  1. liliana
    junio 17, 2008 a las 1:31 am

    Ejemplo de llamada a un método que determina si un número es par o impar

    class metodo1
    {
    public static void main(String arg[ ])
    {
    int a = 5;

    if ( par(a) == true)
    {
    System.out.println(a + ” es par “);
    }
    else
    {
    System.out.println(a + ” es impar”);
    }
    }

    public static boolean par(int num)
    {
    boolean p = false;
    if (num % 2 == 0)
    {
    p = true;
    }

    return p;
    }

  1. julio 7, 2009 a las 3:14 am
  2. octubre 15, 2012 a las 9:44 pm

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s