Recursividad
En programación, una función es recursiva cuando se llama a sí misma.
Uno de los ejemplos más clásicos es el factorial de un número.Para cualquier entero positivo N, el factorial de N (que se expresa como N!) es el producto (multiplicación) de todos los enteros menor a él:
1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 6
4! = 1 x 2 x 3 x 4 = 24
5! = 1 x 2 x 3 x 4 x 5 = 120
6! = 1 x 2 x 3 x 4 x 5 x 6 = 720
Se puede ver que el factorial de cada número incluye el factorial de todos los números anteriores a él. Lo escrito en corchetes rectos a continuación es una referencia, no a nivel matemático:
“2!” es “1[1!] x 2″
“3!” es “(1 x 2)[2!] x 3″
Y así sucesivamente. Para cualquier entero N mayor a 1, podemos decir que el factorial de N es igual al factorial del número anterior a N multiplicado por N. La fórmula N! = (N-1)! x N. Vuelve a la lista de factoriales de 1 a 6. Busca en cada caso los términos que son factorial del número anterior para darte cuenta. Entonces se podría decir que una buena práctica es encontrar el factor en el resultado que se repite.
Pasando esto a función en C, podemos hacer una función a la que le pasamos un número, y nos devuelve el factorial:
int factorial(int n){
return n * factorial(n - 1);
}
Ahí tenemos la función recursiva.
El problema es que la función definida arriba no termina nunca, va a seguir restándole 1 a N por siempre. Siempre vamos a poder restarle 1 a cualquier n, por lo que la función va a seguir ejecutándose a sí misma por siempre. Además, para cualquier número positivo, factorial de n va a devolver 0, porque cualquier multiplicación con 0 como término devuelve 0. Y restarle 1 recursivamente a cualquier entero positivo, eventualmente dará cero.
