Nuevos Programadores

Siguiendo con el tema Recursividad, ahora vamos a ver un ejemplo en C++ que es otro de los clásicos a la hora de aprender algoritmos recursivos, el cálculo del factorial de un número.

El factorial de un número n, se define como el producto de todos los números naturales comprendidos entre 1 y n, o sea que el factorial de 3 es 1 x 2 x 3 = 6. Por definición además, el factorial de 0 es 1.
Veamos lo anterior con ejemplos y a continuación la función iterativa para realizar el cálculo del factorial en C++.

• 3! = 3 x 2 x 1
• n! = n x (n-1) x (n-2) … x 1

int factorial(int n) { 
	int i; 
	int fact = 1; 
	for(i = 1; i <= n; i++) { 
		fact = fact * i; 
	} 
	return fact; 
}

Ahora si analizamos un poco más podemos ver que n! = n x (n-1)! (para n > 0), de donde surge la recursividad, ahora veamos un ejemplo y luego la función recursiva.

• 4! = 4 x 3 x 2 x 1
• 4! = 4 x 3!
• 3! = 3 x 2 x 1
• 3! = 3 x 2!
• 2! = 2 x 1

int factorial(int n) { 
	if(n == 0) { 
		return 1; 
	} 
	else 
	{ 
		return n * factorial(n-1); 
	} 
}

}