¿Qué es la recursividad?

En programación la recursividad es un concepto básico que se enseña cuando das tus primeros pasos de programación, aún así siempre es un tema confuso y que suele causar problemas a los programadores mas maduros también. Ya que antes tonteamos con la definición, ahora toca tratar de explicarla.

Existen varios tipos de recursividad pero todos ocurren cuando una función se llama así misma -aunque sea indirectamente-. Al pensar en esto te preguntaras -acertadamente- si esto no provoca un bucle infinito, pero para evitar este problema se construye una "condición de escape", cuando el número es suficiente pequeño se termina la recursión y se regresa un valor fijo.

Fibonacci al rescate

La sucesión de Fibonacci (si pasaste de noche las clases, la sucesión se conforma de dos números iniciales, donde el siguiente se calcula con la suma de los dos anteriores, es decir; 0,1,1,2,3,5,8,13.. ) es un problema que se utiliza casi siempre para codificar un ejemplo de recursión, su formula sería algo así:

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

Y se puede programar casi literalmente:

function fibonacci($n)
{
    if ( $n <  2 )
        return 1;
    else
        return fibonacci($n-1) + fibonacci($n-2);
}

Esto no es ni de cerca la manera mas eficiente de resolver Fibonacci, pero si es un buen ejemplo de recursión. Como pueden ver la función se va llamando a si misma con cantidades cada vez mas pequeñas hasta que llegamos a la "condición de escape", que nos permite que se termine la recursión y se devuelvan los resultados.

Si colocamos mensajes a la entrada y salida de la función podemos seguir paso a paso la secuencia y entenderlo mejor. Por ejemplo, para n = 4, esto es lo que se despliega:

entrada: 4
entrada: 3
entrada: 2
entrada: 1
salida: 1
entrada: 0
salida: 1
salida: 2
entrada: 1
salida: 1
salida: 3
entrada: 2
entrada: 1
salida: 1
entrada: 0
salida: 1
salida: 2
salida: 5

¿No te queda claro aún? Aquí tienes una mejor explicación: ¿Qué es la recursividad?