Otra forma de entender recursividad en programación

Otra forma de entender recursividad en programación

   febrero 25, 2015       Unknown

---

Un amigo me comentó que jamás entendió recursividad y después de hacerlo sufrir un poco, (como todo buen amigo jeje), le expliqué recursividad a mi manera. Lo primero que le dije fue, - la recursividad es un bucle while desglosado, con la diferencia de que en recursividad regresamos un valor que podría ser utilizado o asignado.- Continua leyendo para que conozcas el porqué.
Nota: Los ejemplos estan realizados en c.

"Se denomina llamada recursiva (o recursividad), a aquellas funciones que en su algoritmo, hacen referencia a sí misma." (Python para principiantes)

Imagina que tenemos que imprimir un texto tres veces con un ciclo while, un ejemplo de esto sería:

int main(void){
    num=3;
    while(num>=1){
        printf("Hola Mundo!!");
        num--;
    }
    return 0;
}

Si esto lo pasamos a una función recursiva quedaría así:

int imprime(int num){
    if ( num>=1 ){
        printf("Hola Mundo!!");        
        return imprime(num-1);
} else {
        return 0;
    }
}

int main(void) {

    imprime(3);
    return 0;
}

Empecemos viendo las similitudes mientras vamos corriendo el código mentalmente:

• Al momento de llamar la función le pasamos el valor de 3, así que la variable num en la función imprime tendrá el valor de tres, igual que en el ejemplo del while.
• Después se comprueba que la variable num sea mayor a 1 en ambos ejemplos, (aquí entra el ciclo while o el primer if y se imprime por primera vez el texto Hola Mundo). 
• En el while se le resta uno a la variable num y empieza nuevamente el ciclo. En la función recursiva se vuelve a llamar a la función imprime, pasando el resultado de la resta (num-1). Por el momento no le pongas atención al return, eso lo explicaré más adelante.
• Nuestra variable num=2, el proceso de comprobación sucede de nuevo, se imprime por segunda vez el texto y se resta nuevamente el valor de uno a la variable num. Esto sucede una vez mas hasta que el valor de la variable num es menor que uno.

Hasta aqui no creo que exista ningún problema, si es así te invito a comentarlo.

Si has notado, el texto se imprime tres veces, el ciclo while debe de terminar en la siguiente comprobación y el if en la función recursiva ya no es verdadera. Hasta este punto la función ha sido llamada cuatro veces y tenemos pendiente el retorno del valor. En este caso, el valor de cero se regresará sin ser utilizado ni asignado. Por ejemplo, si modificamos el código anterior para imprimir el valor que regresa nuestra función el resultado sería.

Hola mundo
Hola mundo
Hola mundo
0

Para explicar el return utilizaré un ejemplo muy utilizado en la enseñanza de las funciones recursivas, que es la obtención del factorial.

#include <stdio.h>
int factorial(int num){
    if (num > 1){
        return num*factorial(num-1);
    } else {
        return 1;
    }
}

int main (void){

    printf("%d\n",factorial(5));
    return 0;
}

Imagina que cuando se llama la función factorial se crea un recuadro, y cada vez que la función factorial se llama a sí misma se crea un nuevo recuadro dentro del anterior. La función deja de llamarse a sí misma hasta que llega la variable num al valor de uno, regresando ese valor.

Cuando se inicia el retorno de los valores, se realizan las operaciones pendientes en el returns anteriores. Tal vez una imagen ayude a entenderlo un poco más.

Es muy importante tener en cuenta que siempre que podamos evitar las funciones recursivas será mejor (ocupa menos memoria de ram y se ejecuta más rápidamente). Pero hay casos donde el usar de recursividad hace mucho más sencillo el desarrollo de un algoritmo.