Recursividad

El término recursividad se puede definir con una sencilla palabra: repetición, en java, siendo más específicos un método recursivo es aquel que llama a si mismo de manera directa o indirecta, también podemos definirla como una técnica de programación que permite que un bloque de instrucciones se ejecute n veces y en ocasiones remplaza a las estructuras repetitivas, y para ello podemos plantear tipos de recursividad.

• Recursión lineal: Este se define como el método que tiene una llamada recursiva y su velocidad estará en función de la rapidez con la cual se acerque nuevamente hacia el caso base. Éste método esta dividido a su vez en:

1. Recursión por llamada en cola: Es cuando la llamada recursiva se hace al final del método.

Para ejemplificar esto tenemos:
int mcd(a, b){
    if( b==0)
       return a;
    else
       return mcd( b, a/b);
}

Lo cual nos arrojará el Mínimo Común Divisor de 2 números.

2. Recursión sin llamada en cola: Se da cuando después de ejecutar la llamada recursiva, el método debe realizar una operación pendiente para completar todo proceso.

Para ejemplificar esto tenemos:
int factorial(n){
    if( n==1)
       return 1;
    else
       return n * factorial(n-1);
}

Lo cual nos arrojará el resultado de la factorial de un número. Como podemos ver, después de haber ejecutado la llamadas recursiva debemos realizar la operación “multiplicación”, para este caso en especifico.

• Recursión no lineal: Sí se da el caso de que haya más de una llamada recursiva por rama del condicional, entonces podemos decir que es un método recursivo es no lineal.

Recursión en cascada: Esta se da cuando en cada rama hay más de una llamada a la función recursiva.

Para ejemplificar esto tenemos:
int fibonacci(n){
    if( n<=1)
       return 1;
    else
       return fibonacci(n-1) + fibonacci(n-2);
}

Lo cual nos arrojará el n-ésimo valor de la serie de Fibonacci.

Recursión en anidada: Es cuando alguna llamada recursiva recibe como parámetro a una llamada recursiva.

Para ejemplificar esto tenemos:
int Ackerman(m, n){
    if (m == 0)
       return n+1;
    else if (m > 0 and n == 0)
       return ackermann(m-1, 1);
    else if (m > 0 and n > 0):
       return ackermann(m-1, ackermann(m, n-1));
}

Lo cual nos arrojará la función Ackerman.

• Recursión mutua: Este método es cuando dos funciones son recurrentes entre sí.

Para ejemplificar esto tenemos:
int impar(n){
    if (n==0)
       return false;
    else
       return par(n-1);

int par(n){
    if (n==0)
       return true;
    else
       return impar(n-1);
}

Lo cual nos arrojará si el parámetro que le enviamos al método es par o impar (donde n es un entero forzosamente).

¿Pero como funciona el método recursivo?

Todos los algoritmos son recursivos cuando, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez. Por lo tanto podemos decir que algo es recursivo si se define en términos de sí mismo o en esencia cuando para definirse hace mención a sí mismo.

La referencia a sí misma debe ser relativamente más sencilla que el caso considerado, todo lo anterior para que una llamada recursiva sea válida.

Este proceso parece que es infinito, pero en términos generales, la clave está en que en cada llamada el problema se va “simplificando” de tal manera que llegará a cierto punto en el cual no hará falta llamar una vez más al método recursivo. Solo por mencionar un ejemplo, es necesario recordar que un árbol tiene ramas y que la rama tiene ramitas más pequeñas, que a su vez tiene más ramitas, pero tarde o temprano va llegar el momento en el cual se llegue a una rama que solo tiene hojas.

Nosotros pensamos que recursividad es una herramienta con mucha importancia en la programación, ya que en todos los casos permite expresar algoritmos de forma más simple y con mayor legibilidad.