OIA-Wiki

Una función recursiva es una función que se define a partir de sí misma. Un ejemplo muy común en el que se puede usar una función recursiva es para calcular la sucesión de fibonacci. Esta sucesión se define como $1$ en las posiciones $0$ y $1$, y en otra posición toma el valor de la suma de los dos números anteriores. La sucesión empieza con los números $1, 1, 2, 3, 5, 8$.

Se ve que el valor de una posición (excepto por los primeros dos), depende de los valores anteriores. Entonces, si $f(n)$ nos dice el valor del enésimo número de esta sucesión, necesitaríamos saber $f(n-1)$ y $f(n-2)$ cuando $n>1$.

Acá entonces se ve cómo es el uso de la recursión. Un sencillo código para calcular el enésimo número de fibonacci podría ser:

int fibo(int n){
    if (n==0 or n==1){
        return 1;
    }else{
        return fibo(n-1)+fibo(n-2);
    }
}

Hay un concepto clave que hay que entender hablando de recursión, que es el de los casos base. Es decir, valores que sabemos a priori cuánto dan, y que son necesarios para calcular todo el resto.

En este ejemplo los casos base eran $n=0$ y $n=1$. Pensar que sin casos base, la función se seguiría llamando a sí mismo indefinidamente y el programa no terminaría.

Otro ejemplo puede ser el de la función factorial. Si bien podemos hacer esto con un for, se puede pensar como una función recursiva: $n! = n*(n-1)!$, si lo escribimos como función queda $f(n) = n*f(n-1)$, tomando como caso base $f(0)=0!=1$ por definición.

Algo con lo que también hay que tener cuidado, es, al implementar una función recursiva, llamar a la función con distintos parámetros a los que están en el estado actual. Digamos, si en el ejemplo de recién hubiéramos puesto $f(n)=n*f(n)$, la función nunca terminaría porque nunca llegaría al caso base.

Un ejemplo de recursión en la vida cotidiana puede verse cuando buscamos una palabra nueva en el diccionario. Partimos de una base de palabras que sabemos, y a partir de ahí queremos aprender una nueva. Leemos la definición. Agarramos las palabras de la definición que no entendimos, y vamos a aprenderlas. Y así sucesivamente hasta que todas las palabras que veamos las conocemos. Entonces usando estas últimas que aprendimos, aprendemos las palabras que usaban a éstas en la definición, y así vamos volviendo aprendiendo todas en el camino hasta que aprendemos la nueva palabra que queríamos. Un código para esta situación, teniendo una función “obtenerDefinicionDeDiccionario” para obtener la definicion de una palabra podría ser:

void aprenderPalabra(palabra){
    definicion = obtenerDefinicionDeDiccionario(palabra)
    for(string palabraEnDefinicion : definicion){
        if(noConozco(palabraEnDefinicion)){
            aprenderPalabra(palabraEnDefinicion);
        }
    }
    // Palabra aprendida!
}

$\large Atencion$: Podría pasar que una palabra aparezca en la definición de una palabra de su definición, por ejemplo si el diccionario dijera “Pie: Parte del cuerpo, usado para caminar”, “Caminar: Acción realizada con los pies”. Si tuviéramos que aprender esas dos palabras, la función entraría en un loop y no terminaría nunca.

Eso es algo de lo que hay que tener cuidado: No necesitar saber el resultado de la función evaluada en dos valores que dependen entre ellos.

La idea general es tratar de resolver un problema a partir del mismo problema, pero más fácil. Y una vez que resolvemos el más fácil, utilizarlo para el más difícil. Este idea se usa en muchos lados, por ejemplo en Divide and Conquer y Programación Dinámica.