Recursividad

Se dice que una función es recursiva cuando su ecuación de solución se utiliza a si misma para resolverse.

Un ejemplo típico de recursividad es la función Factorial, sabemos que el Factorial de un numero es igual al producto de dicho número multiplicado por el factorial del número anterior:

Factorial(4) = 4 * Factorial(3)

Vemos que está definiendo la solución del factorial empleando la misma fórmula del factorial, puesto que:

Factorial(3) = 3 * Factorial(2)
Factorial(2) = 2 * Factorial(1)
....

Pero, ¿Cuándo termina la recursividad? Es absolutamente necesario definir lo que se llama un TOPE, que es cuando la recursividad termina, sino seguiríamos hasta el infinito.

Para el caso del ejemplo típico del factorial, se sabe que esta función se aplica a un conjunto de números enteros mayores o iguales a 0, del cual Factorial(0) = 1, siendo esta fórmula la única que no utiliza la recursividad para su definición, por tanto:

Toda función recursiva necesita un TOPE, dicho tope es una de la soluciones de la función que no se define por si misma.

Si generalizamos podemos decir que, Para toda N tal que N>=0, Factorial(N) se resuelve con las siguientes ecuaciones:

Si N=0, Factorial(N) = 1
Si N>0, Factorial(N) = N * Factorial(N-1)
Para cualquier otro valor de N, No existe conjunto solución para Factorial(N)

Otra característica importante de una función recursiva es que al llamarse a si misma los parámetros deben variar, sino entrará en bucle infinito, por ejemplo esto sería un error:

Factorial(N) = N * Factorial(N)     ---> En este caso caerá en bucle infinito porque NUNCA llegará al TOPE

Por tanto:

En toda función recursiva es necesario que la llamada si misma garantice que en algún punto llegará al TOPE. 

//ejemplo de función recursiva
//asumimos que el valor N que ingresa es >=0
int factorial (int N)
{
    //lo primero que definimos en una función recursiva el el TOPE
    if(N == 0) return 1;
    //La llamada recursiva con N-1 asegura que en algún momento llegará a ejecutar factorial(0)
    return N * Factorial(N-1);
}


¿Por qué es importante definir el tope al principio?
¿Podríamos utilizar la operación unaria -- para llamar de forma recursiva: Factorial(N--)?