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 24:
- 24 = 2 * 2 * 2 * 2 = 16
- 2 * 2 * 2 * 2 = 2 * (23) = 2 * 8 = 16
- 2 * (23) = 2 * (2 * (22)) = 2 * (2 * 4) = 16
Visto lo anterior, podemos afirmar que xy = x * (xy-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 f0 = 0, f1 = 1, un término enésimo se define como fn = fn-1 + fn-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 |
}
