Nuevos Programadores

Utilizaremos JavaScript para estos ejemplos de recursividad.

Una función es recursiva cuando en su cuerpo hay un llamado a si misma, un ejemplo clásico es la operación matemática potencia, primero veamos la función no recursiva que defina la potencia:

function potencia(base, exponente) {
	 if(exponente == 0) { //caso límite de exponente cero
		return 1
	 } else {
		return base * potencia(base, exponente -1) //llamado recursivo
	 }
}

Para este caso tomaremos sólo las potencias de exponente positivo para no aumentar la complejidad del ejemplo.

Lo que haremos a continuación será analizar la función para convertirla en recursiva, primero los casos límite, sabemos que el resultado de toda potencia de exponente 0 es 1, entonces ese será nuestro primer chequeo.

Luego estudiemos la función a partir de un ejemplo, sea en este caso 2⁴:

• 2⁴ = 2 * 2 * 2 * 2 = 16
• 2 * 2 * 2 * 2 = 2 * (2³) = 2 * 8 = 16
• 2 * (2³) = 2 * (2 * (2²)) = 2 * (2 * 4) = 16

Visto lo anterior, podemos afirmar que x^y = x * (x^y-1) de donde claramente se desprende la recursividad, en palabras, potencia de x a la y = x por potencia de x a la y -1, vamos el código:

function potencia(base, exponente) { if(exponente == 0) { //caso límite de exponente cero return 1; } else { while(exponente >= 1) { return base * potencia(base, exponente -1); //llamado recursivo } } } 

Tal vez en este caso no es muy notorio, pero una de las principales ventajas de utilizar algoritmos recursivos es la disminución de la cantidad de líneas de código necesarias.

Estudiemos el caso de la sucesión de Fibonacci, otro ejemplo clásico de algoritmo recursivo.

Cada término de la sucesión de Fibonacci es la suma de los 2 términos predecesores, sabiendo que los primero términos, por definición son 0 y 1, entonces sabemos que los primeros 10 términos de la sucesión son:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Ahora podemos afirmar que además de los términos primarios f₀ = 0, f₁ = 1, un término enésimo se define como f_n = f_n-1 + f_n-2

Veamos una función recursiva que calcule el término n de la sucesión de Fibonacci:

function fibonacci(n) {
	if(n==0 || n== 1) { // casos límite 
		return n; 
	} else { 
		return fibonacci(n-1) + fibonacci(n-2); // suma del término anterior y su predecesor 
	} 	
}

Si llamamos a la función anterior en un bucle podremos obtener la sucesión hasta el término especificado en el bucle, por ejemplo:

var fib = "F: "; 
for(i = 0; i<= 9; i++) { 
	fib += fibonacci(i) + " | "; 
} 
document.write(fib);

Nos escribirá los primeros 10 términos de la sucesión de Fibonacci: F: 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |

También te puede interesar:

• Convertir un entero base 10 a binario en Java (Recursivo)
• Factorial en C++ - Función recursiva vs. función iterativa
• Métodos de extensión en VB.NET (Extension Methods)
• Validar formularios web con JavaScript y Expresiones Regulares
• Como reemplazar texto de un documento usando JavaScript y expresiones regulares