En general, un concepto es recursivo cuando en su definición se emplea el concepto que se está definiendo. Desde el punto de vista de la programación, una función es recursiva cuando se llama a sí misma.
La recursividad es otra forma de abordar la solución de problemas repetitivos. Algunos problemas pueden ser resueltos de manera más sencilla y clara siguiendo el razonamiento recursivo, mientras que otros pueden ser resueltos de manera más sencilla y clara siguiendo el razonamiento iterativo.
En el razonamiento iterativo se piensa en la estructura más adecuada para repetir un proceso y en la condición más adecuada para concluir las repeticiones. En el razonamiento recursivo se piensa en como resolver el problema empleando el resultado devuelto por una llamada a sí misma, además, la función recursiva debe contar con una condición que, al cumplirse, devuelva un resultado conocido.
Cada vez que una función recursiva se llama a sí misma, se crea una copia de la función en memoria. Cada una de estas copias permanece en memoria hasta que una de las llamadas devuelve el resultado conocido. Entonces la copia que recibe el resultado termina de ejecutarse y devuelve un resultado, con el cual termina y devuelve un resultado la copia previa y así sucesivamente hasta llegar a la primera copia (la primera llamada recursiva), la que también termina de ejecutarse y devuelve el resultado final.
Algo que se debe tener presente, al momento de resolver un problema de forma recursiva, es que el mecanismo, es decir el cómo la función se llama a sí misma no es parte del problema, de ello se encarga el lenguaje de programación, sin embargo, se debe comprender perfectamente la lógica recursiva, es decir qué sucede cuando se hace una llamada recursiva y qué sucede cuando una llamada recursiva concluye, porque de lo contrario no es posible deducir, plantear e implementar correctamente, una solución recursiva.
Hasta familiarizarse con el razonamiento recursivo, las soluciones recursivas pueden parecer más difíciles que las iterativas, sin embargo, las soluciones recursivas existen únicamente porque son más sencillas que su contraparte iterativa. Si una solución recursiva resulta más complicada y/o más larga, que su contraparte iterativa, entonces o la solución ha sido mal planteada o, por su naturaleza, la solución es iterativa.
Las soluciones recursivas consumen más memoria y requieren más tiempo que las soluciones iterativas: cada llamada recursiva crea una copia de la función y luego, cuando cada una de esas copias devuelven un resultado, se elimina la copia. Esas operaciones consumen no sólo memoria, sino también tiempo, siendo la razón por la cual las soluciones recursivas son menos eficientes que las iterativas. Por esa razón, sólo se justifica la creación de funciones recursivas cuando dichas soluciones son más sencillas que su contraparte iterativa.
Ejemplos
Factorial de un número
En ete ejemplo, se programa un método recursivo que calcula el factorial del número entero desde el cual es llamado.
Para comprender la diferencia entre el razonamiento iterativo y recursivo, se recuerda que, desde el punto de vista iterativo, el factorial de un número es la productoria de los números que existen entre 1 y dicho número, es decir:
\[
n! = \prod_{i=1}^{n} i
\]
Por lo tanto, iterativamente, la solución consiste en un ciclo for que va desde 1 hasta el número cuyo factorial se quiere calcular y en cuyo interior se calcula la productoria del contador del ciclo. El código, implementado como un método dinámico estándar de la clase Number, es:
function factorial(n) { let f = 1; for (let i=1; i<=n; i++) f *= i; return f; };
Con la cual, se obtienen los resultados correctos:
factorial(0)
factorial(1)
factorial(5)
factorial(7)
factorial(17)
factorial(25)
Observe que, en cada repetición del ciclo, se calcula un factorial, así en la segunda repetición del ciclo se calcula el factorial de 2, en la tercera el de 3 y así sucesivamente hasta que, en la última repetición, se calcula el factorial de "n". Por ejemplo, en la cuarta repetición se calcula el factorial de 4 multiplicando el resultado de la iteración anterior (el factorial de 3) por 4, es decir:
\[
4! = 3!\times 4 = 6\times 4 = 24
\]
Igualmente, en la quinta repetición, se calcula el factorial de 5 multiplicando el resultado de la anterior iteración (el factorial de 4) por 5:
\[
5! = 4!\times 5 = 24\times 5 = 120
\]
Entonces, en general, el factorial de "n" se calcula multiplicando el factorial de la iteración anterior, el factorial de "n-1", por "n":
\[
n! = (n-1)!\times n
\]
Y esta fórmula es una fórmula recursiva: para calcular el factorial de "n", la función se llama a si misma con "n-1" y se multiplica el resultado de la llamada recursiva por "n". Como se ha comprobado en los ejemplos previos (para el factorial de 4 y 5) el razonamiento es correcto, porque se obtienen lo resultados correctos. En consecuencia, la lógica recursiva ya ha sido verificada.
Sin embargo, para completar la solución recursiva hace falta la condición para la cual se conoce un resultado. En este caso se sabe, por definición matemática, que el factorial de 0 es 1 y dado que en cada llamada recursiva el valor de "n" disminuye en 1 (hasta llegar a 0), esa es la condición de finalización correcta para este problema. Es decir que: la función recursiva debe devolver 1 cuando "n" es 0.
Entonces, algoritmo recursivo con el que se resuelve el problema es:
A primera vista el algoritmo puede parecer inclusive erróneo, por lo que es necesario analizar el mismo.
Por ejemplo, para calcular el factorial de 5 (n=5), la función intenta evaluar la expresión: factorial(5-1)*5 = factorial(4)*5 y con ese fin se llama a si misma, pero con n=4, mientras tanto (hasta que se conozca el valor del factorial de 4) el cálculo del factorial(4)*5, queda pendiente.
Entonces el programa pasa a la llamada recursiva con n=4 y (como "n" no es cero) intenta evaluar la expresión: factorial(4-1)*4 = factorial(3)*4 y con ese fín, se llama a si misma con n=3, mientras tanto, el cálculo del factorial(3)*4 queda pendiente.
Ahora el programa pasa a la llamada recursiva con n=3 y (como "n" no es cero) intenta evaluar la expresión: factorial(3-1)*3 = factorial(2)*3 y con ese fín, se llama a si misma con n=2, mientras tanto, el cálculo del factorial(2)*3 queda pendiente.
Luego el programa pasa a la llamada recursiva con n=2 y (como "n" no es cero) intenta evaluar la expresión: factorial(2-1)*2 = factorial(1)*2 y con ese fín, se llama a si misma con n=1, mientras tanto, el cálculo del factorial(1)*2 queda pendiente.
Luego el programa pasa a la llamada recursiva con n=1 y (como "n" no es cero) intenta evaluar la expresión: factorial(1-1)*1 = factorial(0)*1 y con ese fín, se llama a si misma con n=0, mientras tanto, el cálculo del factorial(0)*1 queda pendiente.
Entonces, el programa pasa a la llamada recursiva con n=0 y como ahora "n" es cero, la función devuelve 1 (el factorial de 0).
Ese resultado (1) es devuelto a la expresión cuyo cálculo quedó pendiente y como ahora ya se tiene el valor (1) la expresión es evaluada: factorial(0)*1 = 1*1 = 1 y el resultado (1) es devuelto.
El resultado (1) es devuelto a la expresión cuyo cálculo quedó pendiente: factorial(1)*2 = 1*2 = 2 y el resultado (2) es devuelto.
El resultado (2) es devuelto a la expresión cuyo cálculo quedó pendiente: factorial(2)*3 = 2*3 = 6 y el resultado (6) es devuelto.
El resultado (6) es devuelto a la expresión cuyo cálculo quedó pendiente: factorial(3)*4 = 6*4 = 24 y el resultado (24) es devuelto.
El resultado (24) es devuelto a la expresión cuyo cálculo quedó pendiente: factorial(4)*5 = 24*5 = 120 y el resultado (120) es devuelto, en este caso (como ya no existen más llamadas recursivas) el resultado es devuelto al programa (o aplicación) que hizo la llamada inicial.
En consecuencia, al finalizar el proceso, el método devuelve 120 (que es el factorial de 5).
Como se puede apreciar en este ejemplo, el proceso recursivo es moroso, sin embargo, de ese proceso se encarga el lenguaje, por lo que el proceso en sí, no es parte del problema. Lo importante es comprender la lógica involucrada y generalmente esa lógica es sencilla: El método se llama a si mismo, disminuyendo en cada llamada el valor de "n" en 1, hasta que "n" es igual a 0, momento en el cual se obtiene la primera respuesta (1). Con esa respuesta se calcula el factorial de 1, con el factorial de 1 el de 2, con el de 2 el de 3 y así, sucesivamente, hasta calcular el factorial del número "n" con el cual se hizo la llamada original.
El código respectivo, implementado como una función estándar, es:
function factorial(n) { return n===0 ? 1 : factorial(n-1)*n; };
Que, por supuesto, devuelve los mismos resultados que la versión iterativa:
factorial(0)
factorial(1)
factorial(5)
factorial(7)
factorial(17)
factorial(25)
Sin embargo, dado que casi siempre no sólo se debe calcular el resultado, sino que además se debe validar que él o los datos recibidos sean correctos, es más claro y eficiente programar el proceso recursivo en una función interna y no en el método en sí, tal como se muestra en el siguiente código, donde se valida que el número sea entero y positivo:
function factorial2(n) {
if (n%1!==0 || n<0) throw new Error("El número debe ser entero positivo");
const factorial = n => n===0 ? 1 : factorial(n-1)*n;
return factorial(n);
};
Que, por supuesto, devuelve los mismos resultados que la versión anterior, pero que además valida que el número sea entero y positivo.
factorial2(0)
factorial2(1)
factorial2(5)
factorial2(7)
factorial2(17)
factorial2(25)
factorial2(12.53)
factorial2(-12)
Si el proceso recursivo no se implementa en una función interna, la validación se haría (inútilmente) cada vez que el método se llama a si mismo. Por ejemplo, al calcular el factorial de 25, el método validaría 25 veces, que el número recibido sea entero y positivo, cuando se sabe desde la primera llamada si el número es entero y positivo y esa condición no cambia en ninguna de las llamadas recursivas, porque, en cada llamada recursiva, el número disminuye en 1 pero sólo hasta 0, que es el valor para el cual se conoce el factorial. En consecuencia, si el número es entero y positivo en la primera llamada recursiva, seguriá siendo entero y positivo en todas las llamadas subsecuentes.
Número de dígitos de un número
En este ejemplo se programa una función que devuelve el número de dígitos del número entero positivo desde el cual es llamado.
Si se conoce el número de dígitos del número sin su último dígito, el número de dígitos del número simplemente es ese número más uno, por ejemplo, si el número es 1234567 y se conoce el número de dígitos de 123456 (que obviamente es 6), entonces el número de dígitos de 1234567, simplemente es: 6+1=7 (que es el resultado correcto). Por lo tanto, el número de dígitos de un número puede ser calculado sumando 1 al número de dígitos del número sin su último dígito.
El número sin su último dígito simplemente es el cociente del número entre 10. Entonces, la función recursiva se llama a sí misma con el cociente del número entre 10, hasta que el número no tiene más dígitos, es decir hasta que el número es cero, porque el cociente de un número menor o igual a 9 (entre 10) es 0, siendo esa la condición de finalización del algoritmo recursivo,
El diagrama de flujo para la solución recursiva planteada, es:
var numDígitos = function(n) {
if (n%1!==0 || n<0) throw 'El número debe ser entero positivo';
const numdígitos = n => n===0 ? 0 : numdígitos(Math.quot(n,10))+1;
return numdígitos(n);
};
Llamando al método con algunos valores de prueba, se obtiene:
numDígitos(1234567)
numDígitos(403829)
numDígitos(324)
numDígitos(21)
numDígitos(9)
numDígitos(0)
numDígitos(-134932)
numDígitos(31245.66)
Sumatoria de números impares
En este ejemplo se programa un método que devuelve la sumatoria de los "n" primeros números impares.
La sumatoria de los primeros "n" números impares, desde el punto de vista recursivo, es la sumatoria de los primeros "n-1" números impares más el valor del número impar en la posición "n" (2*n-1). Así, la sumatoria de los primeros 5 números impares (1+3+5+7+9), es igual a la sumatoria de los primeros 4 números impares (1+3+5+7=16), más el valor del quinto número impar (2*5-1=9), es decir: 16+9=25.
Entonces, de manera similar a los otros casos, la función se llama a sí misma, con un valor de "n" igual a "n-1", hasta que el valor de "n" es cero, valor para el cual se sabe la respuesta: la sumatoria de 0 números impares es simplemente 0.
La lógica de la solución recursiva, en forma de diagrama de flujo, es:
var sumImpares = n => {
if (n%1!==0 || n<0) throw 'El número debe ser entero positivo';
const sumImpares = n => n===0 ? 0 : sumImpares(n-1)+2*n-1;
return sumImpares(n);
};
Llamando al método con algunos valores de prueba, se obtienen los resultados correctos:
sumImpares(0)
sumImpares(5)
sumImpares(10)
sumImpares(500)
sumImpares(1000)
sumImpares(-600)
sumImpares(125.33)
Potencia entera
En este ejemplo se programa un método que devuelve la potencia entera "n" del número real "x" desde el cual es llamado.
De forma similar a los anteriores ejemplos, la potencia "n" de un número "x", puede ser calculada comprendiendo que es igual a la potencia "n-1" del número "x", multiplicada por x. Así, por ejemplo, 25 es igual a 24*2 = 16*2 = 32. Entonces la función se llama a sí misma disminuyendo en 1 el valor de la potencia, hasta que la potencia (n) es cero, momento en el cual se conoce la respuesta, pues un número elevado a 0 es 1, siendo esa la condición de finalización del algoritmo recursivo.
La lógica de esta solución, en forma de diagrama de flujo, es:
Observe que en la llamada recursiva no se manda la base "x", sino únicamente la potencia "n-1". Se procede así porque la base "x" es constante, razón por la cual no tiene sentido mandar, en cada llamada recursiva, un valor que no cambia nunca.
Y el código respectivo, implementao como una función estándar, es:
function potEntera(x, n) {
if (n%1!==0 || n<0) throw "El exponente debe ser entero positivo";
const potEntera = n => n==0 ? 1 : potEntera(n-1)*x;
return potEntera(n);
};
Llamando al método con algunos valores de prueba, se obtiene:
potEntera(1.2, 0)
potEntera(2.1, 5)
potEntera(0.25, 7)
potEntera(2, 8)
potEntera(1.5, 25)
potEntera(-6.7, 10)
potEntera(3.2, -20)
potEntera(4.2, 5.6)
Que son los resultados correctos, no obstante, esta solución es, desde el punto de vista lógico, incorrecta, porque implica la repetición innecesaria de muchas operaciones. Así, para calcular 3.42500000, se requieren ¡2 millones quinientas mil llamadas recursivas!, lo que implica la creación y destrucción de ¡2 millones quinientas mil copias del entorno de la función (variables y estado de ejecución)!.
Se reduce a la mitad el número de llamadas recursivas, evitando ¡1 millón ciento veinticinco mil! llamadas recursivas. Aplicando nuevamente el mismo procedimiento a la potencia restante, se reduce igualmente a la mitad el número de llamadas recursivas. Procediendo de esa manera con cada una de las potencias restantes, se reduce considerablemente el número de llamadas recursivas, así como el número de operaciones necesarias.
Por ejemplo para calcular el valor de:
\[
x^{4561}
\]
Se lleva a cabo la siguiente operación:
\[
x^{4561} = \left( x\raisebox{0.9em}{$\frac{4561-1}{2}$}\right)^2 \cdot x = \left(x ^{2280}\right)^2 \cdot x
\]
Donde a la potencia se le resta 1 para que la división sea exacta y por esa misma razón, se multiplica por "x". Luego la nueva potencia (x2280), se calcula con:
Que implica un total de 13 repeticiones y 18 multiplicaciones, en lugar de ¡4561 repeticiones y 4561 multiplicaciones! (99.6% menos operaciones que en la versión anterior).
Se trata entonces de una solución mucho más eficiente, cuyas expresiones generales, son:
\[
\begin{aligned}
x^{n} &= \left( x\raisebox{0.9em}{$\frac{n}{2}$}\right)^2
&&\begin{cases}\text{cuando "n" es par}\end{cases}\\[3mm]
x^{n} &= \left( x\raisebox{0.9em}{$\frac{n-1}{2}$}\right)^2 \cdot x
&&\begin{cases}\text{cuando "n" es impar}\end{cases}
\end{aligned}
\]
Al igual que en el anterior planteamiento, cuando la potencia es 0, se conoce el resultado: 1 (porque cualquier número elevado a 0 es 1), por lo tanto esa sigue siendo la condición de finalización.
Por otra parte, la función se llama a si misma con la mitad de la potencia (n/2) y el resultado devuelto se eleva al cuadrado. Si la potencia es impar (si n%2 es igual a 1) ese resultado se multiplica por "x", caso contrario (si es par) se multiplica por 1, es decir por el resultado de: n%2 ? x : 1.
var potEntera_ = function(x, n) {
if (n%1!==0 || n<0) throw "El exponente debe ser entero positivo";
const potEntera = n => n===0 ? 1 : potEntera(Math.quot(n,2))**2*(n%2?x:1);
return potEntera(n);
};
Llamando a la función, se obtienen los mismos resultados que con la versión anterior:
potEntera_(1.2, 0)
potEntera_(2.1, 5)
potEntera_(0.25, 7)
potEntera_(2, 8)
potEntera_(1.5, 25)
potEntera_(-6.7, 10)
potEntera_(3.2, -20)
potEntera_(4.2, 5.6)
Como ejercicio libre, elabore el algoritmo para resolver este problema, pero de forma iterativa. Al hacerlo se dará cuenta del por qué se afirma que las soluciones recursivas son más sencillas (aunque no más eficientes) que sus contrapartes iterativas.
Ecuación de Ackerman
En este ejemplo, se elabora un método para calcular el valor de la ecuación de Ackerman:
La ecuación de Ackerman es, de hecho, una fórmula recursiva (doblemente recursiva), que tienen definidas las condiciones de finalización, por lo que puede ser transcrita, directamente, a un diagrama de flujo:
LLamando a la función con los valores de prueba, se obtiene:
ackerman(0, 0)
ackerman(1, 3)
ackerman(3, 3)
ackerman(3, 9)
ackerman(4, 0)
ackerman(2, -5)
ackerman(3.1, 2)
Aun cuando la solución de este problema es directa y sencilla, al ser doblemente recursiva, el número de llamadas crece exponencialmente, superando las decenas de millones, razón por la cual no es posible, por ejemplo, calcular el Ackermann de (4, 1):
ackerman(4, 1)
Fibonacci de un número
En este ejemplo se elabora un método que calcula el Fibonacci enésimo ("n") de un número entero positivo:
Como se puede ver, la ecuación de Fibonacci, es una ecuación recursiva (doblemente recursiva), por lo que (al igual que Ackerman) puede ser programada directamente, siendo el diagrama de flujo:
function fibonacci(n) {
if (n%1!==0 || n<=0) throw "El número debe ser entero y mayor a cero";
const fibonacci = n => n===1 || n===2 ? 1 : fibonacci(n-1)+fibonacci(n-2);
return fibonacci(n);
};
Llamando a al método con algunos valores, relativamente pequeños, se obtienen los resultados eperados:
fibonacci(5)
fibonacci(10)
fibonacci(15)
fibonacci(21)
fibonacci(-23)
fibonacci(4.5)
Sin embargo, al intentar calcular el Fibonacci de números más grandes, por ejemplo 50, la página queda como colgada y esto se debe a que la función se está llamando a si misma millones de veces porque el algoritmo recursivo directo es extremadamente ineficiente (puede hacer la prueba, pero guardando previamente el capítulo).
Para comprender por qué esta lógica es tan ineficiente, veamos las llamadas recursivas que se requieren para calcular el Fibonacci de 6:
Donde, como se puede ver, se calcula 3 veces el Fibonacci de 1, 5 veces el Fibonacci de 2, 3 veces el Fibonacci de 3 y 2 veces el Fibonacci de 4.
El número de cálculos repetitivos, innecesarios, incrementa geométricamente con el número de Fibonacci a calcular, así en el Fibonacci de 6 se calculan 9 veces los mismos valores, pero en el Fibonacci de 34 ese número asciende a más de 11 millones, algo absolutamente irracional.
Por lo tanto, es necesario corregir la lógica recursiva, de manera que se evite calcular una y otra vez (irracionalmente) los mismos valores.
Al analizar la fórmula recursiva, se puede ver que como primero se llama al Fibonacci de n-1 y luego al Fibonacci de n-2, el Fibonacci de n-2 ya debe haber sido calculado al calcular el Fibonacci de n-1 (porque para calcular el Fibonacci de n-1, se calcula el Fibonacci de n-2). Por lo tanto, en realidad no es necesario hacer la segunda llamada recursiva, sino guardar y emplear los valores calculados en la primera llamada recursiva.
En consecuencia, si se guardan los valores calculados en un array, se pueden emplear directamente los valores guardados en lugar de volver a calcularlos.
No obstante, para que los valores almacenados en el array permanezcan en memoria y no se pierdan al salir de la función, se debe emplear una clausura (closure). Una clausura es simplemente una función que ha sido devuelta por otra función (es el resultado de otra función). Se caracteriza porque tiene acceso a todas las variables de la función que la devuelve (de la función generadora), inclusive cuando ya no es posible acceder a esa función.
Casi siempre, cuando se trabaja con una clausura, la función que la devuelve solo es llamada una vez, para que devuelva la clausura. Posteriormente solo se trabaja con la clausura, por lo que no se requiere más la función generadora. Por esa razón, en la mayoría de los casos, la función generadora es una función inmediatamente invocada (una IIFE).
En la función generadora (que no requiere ningún dato) se debe declarar el array con los valores iniciales del Fibonacci: [0, 1, 1], no [1, 1], porque el primer índice de un array es 0, no 1 y cada índice debe corresponder al valor respectivo del Fibonacci. Es importante hacer notar que, una vez devuelta la clausura, el array puede ser utilizado/modificado únicamente por la clausura, ninguna otra función o instrucción puede utilizar o modificar ese array o ninguna de las variables declaradas en la función generadora, las cuales, en consecuencia, quedan protegidas.
La función generadora debe devolver la función recursiva para el cálculo del Fibonacci, donde, en la condición de finalización, se pregunta si el número cuyo Fibonacci se está calculando es menor al número de elementos del array y de ser así se devuelve el valor guardado, caso contrario, la función se llama a si misma (con n-1) y se le suma el Fibonacci de n-2 (que, con seguridad, ya ha sido calculado previamente), tal como se puede ver en el siguiente diagrama de flujo que corresponde a la lógica de la clausura y donde fi es el array con los valores calculados del Fibonacci:
>El código respectivo, donde la clausura es generada en una IIFE, programada como una función anónima y guardada en la variable fibo, es:
var fibo = (function() {
const fi = [0,1,1];
return n => n<fi.length ? fi[n] : fi[n]=fibo(n-1)+fi[n-2];
})();
Con el cual, como no se vuelven a calcular los mismos valores, es posible calcular el Fibonacci de números mucho más grandes (hasta que se rebasa máximo número permitido por el lenguaje: Number.MAX_VALUE):
fibo(5)
fibo(10)
fibo(39)
fibo(50)
fibo(100)
fibo(200)
Por supuesto, la clausura, que es únicamente la función recursiva, no valida que el número sea entero positivo. Para ese propósito se debe crear otra función, donde se haga la validación y luego se llame a la clausura para calcular el Fibonacci:
function fibonacci(n) {
if (n%1!==0 || n<=0) throw "El número debe ser entero y mayor a cero";
return fibo(n);
};
Que, obviamente, devuelve los mismos resultados, pero donde además se valida que el número sea entero y mayor a 0.
