La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función.
Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de llamadas recursivas.
Usualmente los lenguajes de programación permiten definir funciones de manera recursiva. El lenguaje C es uno de ellos. La definición recursiva para el factorial sería:
int factorial(int n) {
if ((n == 0) || (n == 1))
return(1);
else
return(n*factorial(n-1));
}
Normalmente las definiciones recursivas pueden expresarse en forma no recursiva. Sin embargo, dependiendo del caso, el resultado puede ser más confuso. Por ejemplo, una función en C que calcula el factorial en forma iterativa sería:int factorial(int n) {
int i, fact = 1;
for (i=2; i<=n; i++)
fact = fact * i;
return(fact);
}Ejemplos:- Factorial -- n! = n × (n-1)!
- Sucesión de Fibonacci -- f(n) = f(n-1) + f(n-2)
- Números de Catalan -- C(2n, n)/(n+1)
- Las Torres de Hanói
- Función de Ackermann
