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 que involucran procesos repetitivos. Mientras que en el razonamiento iterativo se piensa en la estructura y la condición de finalización más adecuada para resolver el problema, en el razonamiento recursivo se piensa en la llamada recursiva que resuelve el problema y en la condición base para la cual se conoce una solución al problema.
En ete ejemplo, se programa una función recursiva que recibe un número entero positivo y devuelve el factorial de ese número.
Como se recordará, el factorial de un número es simplemente la multiplicación de los números enteros que existen entre 1 y el número cuyo factorial se quiere calcular. Así, el factorial de 5 se calcula con: 1*2*3*4*5 = 120, pero como 1*2*3*4 es el factorial de 4, en realidad el factorial de 5 se está calculando con:
| \[ 5! = 4!\times 5 = 24\times 5 = 120 \] |
Igualmente, el factorial de 6 se calcula con:
| \[ 6! = 5!\times 6 = 120\times 6 = 720 \] |
Entonces, para cualquier número entero "n" se cumple que:
| \[ n! = (n-1)!\times n \] |
Y esta fórmula es una fórmula recursiva: para calcular el factorial de un número (de "n") se requiere el factorial de otro número (de "n-1"), siendo esta la llamada recursiva que resuelve el problema, sin embargo, para que la solución esté completa se requiere además la condición base, es decir la condición para la cual se conoce la solución del problema. En este caso, se sabe que (por definición) que el factorail de 0 es 1, por lo que esa es la condición base adecuada para resolver este problema.
Entonces, la función recursiva que resuelve el problema, es:
Como se puede ver, la solución tiene sólo una instrucción. El que las soluciones recursivas sean más sencillas de programar que sus contrapartes iterativas, es la principal razón por la que son empleadas en la práctica.
Llamando a la función, con algunos valores de prueba, se obtienen los resultados esperados:
Si bien esa es la solución recursiva (con una sola instrucción) y como se ha comprobado devuelve los resultados correctos, es está asumiendo que siempre es llamada con valores valores correctos: Números enteros positivos. Como en la práctica no se puede garantizar que el usuario mande siempre los valores correctos, es necesario validar el número recibido para garantizar que realmente sea entero positivo, porque de lo contrario, al mandar un valor negativo o un número real, como en los siguientes ejemplos:
Javascript lanza un error, informando que se ha superado el máximo de llamadas recursivas permitidas: Actualmente los navegadores limitan el número de llamadas recursivas para evitar los ciclos recursivos infinitos. En este caso se supera el límite porque cuando "n" es negativo y en dado que en cada llamada recursiva se le resta 1, nunca llegará a ser cero, por el contrario, se alejará cada vez más y más de cero. Cuando "n" es real, al restarle 1 seguirá siendo real, porque seguirá teniendo su parte fraccionaria, por lo tanto siempre será diferente de cero.
Por esa razón, en la práctica, es necesario programar la función recursiva dentro de otra función, donde se hacen las validacines e inicializaciones que fueran necesarias, antes de llamar a la función recursiva. Así en este caso, en la función externa se valida que el número sea entero positivo y solo entonces se llama a la función recursiva:
Observe que ahora, como se sabe que el número es entero y positivo, se ha cambiado la condición base a n<2 de manera que devuelva 1 tanto para n=0, como para n=1. Esta condición no puede ser empleada sin la validación, porque con un número negativo esta condición sería siempre verdadera (porque todo número negativo es menor a 2) y en consecuencia la función recursiva devolvería 1. Con un número real también, en algún momento, "n" llegaría a ser menor a 2 (porque en cada llamada recursiva se le resta 1) y en ese momento devolvería 1 y comenzaría a calcular un resultado erróneo (porque no existe el factorial de un númeoro real).
Por supuesto, con esta versión, se obtienen los mismos resultados que con la versión anterior:
Si bien el mecanismo de las llamadas recursivas no forma parte del problema, porque de ello se encarga el lenguaje de programación, es útil comprender como funciona para no cometer errores lógicos. En el caso del factorial, por ejemplo, para calcular el factorial de 5 la función se llama sucesivamente con valores de "n" iguales a 4, 3, 2 y 1, entonces (cuando "n" es 1) se cumple la condición base (1 es menor que 2), por lo que devuelve la solución conocida 1, con ese resultado se calculan sucesivamente los factoriales de 2 (factorial(1)*2=1*2=2), el de 3 (factorial(2)*3=2*3=6), el de 4 (factorial(3)*6=6*4=24) y finalmente el de 5 (factorial(4)*5=24*5=120)
Aunque, las soluciones recursivas son más sencillas que su contraparte iterativa, desde el punto de vista de la eficiencia (uso de recursos) son menos eficientes que las iterativas: cada llamada recursiva crea una copia de la función en memoria y cada vez que una de las copias termina (devuelve un resultado) la copia es eliminada de memoria, lo que consume tanto tiempo de procesamiento como memoria.
Varios de los problemas que involucran productorias o sumatorias tienen, esencialmente, la misma lógica que el cálculo del factorial. Por ejemplo, la sumatoria de los primeros "n" números enteros (1+2+3+...+n) puede ser calculada conociendo la sumatoria de los primeros "n-1" números:
| \[ sne(n) = sne(n-1)+n \] |
Cuando "n" es cero, la sumatoria es cero (porque no hay nada que sumar), siendo esa la condición base (la solución conocida). La función recursiva respectiva (sin validación) es:
Igualmente, el cálculo de xn: La potencia entera "n" de un número real "x", se resuelve con la siguiente ecuación recursiva:
| \[ penr(x,n) = penr(x,n-1)*x \] |
En este caso, para la condición base, se sabe que x0 es 1. La función respectiva (sin validación), es:
Por supuesto, en la implementación final (para prevenir errores, así como ciclos recursivos infinitas) es necesario validar los datos. Si es posible, es conveniente, también, mejorar la eficiencia de los cálculos empleando variables locales. En este ejemplo, se debe validar que "n" sea entero positivo y es posible mejorar la eficiencia, empleando el valor de "x" recibido en la función externa, en lugar de mandar una y otra vez (en cada llamada recursiva) el mismo valor (pues el valor de "x" no cambia). La función que mejora la eficiencia (sin validación) es:
Observe que la función recursiva propiamente (pot), sigue siendo muy sencilla y solo tiene una instrucción.
Para calcular recursivamente la sumatoria de los números pares que existen entre 2 y un número "n" dado, se tiene por lo menos dos alternativas.
Por un lado, conociendo la sumatoria de los primeros "n-2" números pares, la sumatoria se calcula sumándole el último número par "n":
| \[ snp(n) = snp(n-2)+n \] |
Cuando "n" es menor a 2 (cuando ya no existen más números pares) la sumatoria es 0 (condición base). Por ejemplo, si "n" es 8, la función se llama a sí misma con 6, 4, 2 y 0, entonces (cuando ya no existen más números pares) devuelve 0 y con ese resultado se calculan y devuelven, sucesivamente: 0+2=2, 2+4=6, 6+6=12 y 12+8=20. La función recursiva programada con este razonamiento (sin validación) es:
Sin embargo, esta solución solo devuelve los resultados correctos cuando el número "n" que recibe es par. Si se manda un número impar, por ejemplo 9:
Se obtiene 24 (la sumatoria de 3+5+7+9) en lugar de 20 (la sumatoria hasta 8: último número par antes del 9). Para obtener la solución correcta, la función recursiva debe ser programada dentro de otra función y llamada con "n-1" (en lugar de "n") si es impar:
Por otra parte, si se conoce la suma de los números pares de 4 a n, basta añadir 2 —el primer número par— para obtener la sumatoria:
| \[ snp3(n,i=2) = snp3(n,i+2)+i \] |
Si "i" supera a "n", la función devuelve 0 porque ya se sumó el último número par (condición base). Por ejemplo, para "n=8", la función se llama a sí misma con "i" igual a 4, 6, 8 y 10. Cuando se cumple la condición base (10>8), devuelve 0; a partir de ese valor, calcula y retorna sucesivamente: 0+8=8, 8+6=14, 14+4=18 y 18+2=20. La función recursiva correspondiente, sin validación, es:
Como se observa, los resultados son correctos incluso cuando el número es impar. Sin embargo, la eficiencia puede mejorarse al incluir el procedimiento en otra función, lo que evita enviar repetidamente el mismo valor de "n":
Este mismo algoritmo también permite calcular la suma de los números pares comprendidos entre dos límites, «m» y «n»:
También se puede adaptar el algoritmo (simplemente cambiando la condición base) para que devuelva la sumatoria de los primeros "n" números pares:
El mismo razonamiento es válido para progresiones (series) tanto aritméticas como geométricas. Por ejemplo, la siguiente función calcula (sin validación) la sumatoria, entre "m" y "n", de la serie aritmética cuya diferencia es 4:
De manera similar, la siguiente función calcula (sin validación) la sumatoria, entre "m" y "n", de la serie geométrica cuya razón es 3 :
Como otro ejemplo, se elabora la función recursiva que devuelve el primer dígito de un número. El primer dígito de un número simplemente es el primer dígito del cociente de ese número entre 10. Por ejemplo, el primer dígito de 8434, es el primer dígito del 843, es decir el número 8. Cuando el número tiene sólo un dígito, ese es su primer dígito, siendo esa lacondición base.
La función recursiva (sin validación) es:
El número de dígitos de un número, recursivamente, simplemente es el número de dígitos de su cociente entre 10 más 1. Así si el número es 12345, su número de dígitos es el número de dígitos de 1234 (4) más 1 (5). Cuando el número tiene solo un dígito (cuando es menor a 10) el número de dígitos es 1 (condición base):
El número sin su primer dígito, se obtiene tomando en cuenta que es el cociente del número entre 10 sin su primer dígito, más el residuo del número entre 10. Por ejemplo, si el número es 54321, el número sin su primer dígito es 432*10+1 = 4321, donde 432 es el cociente ((54321-54321%10)/10=5432) sin su primer dígito y 1 es el residuo del número (54321%10=1). Es necesario multiplicar el cociente por 10, para que el residuo pase a ser el último dígito del número (si se suma directamente el residuo, el resultado sería 432+1=433). Por otra parte, cuando el número tiene un dígito (cuando es menor a 10) sin su primer dígito es 0, siendo esa la condición base.
La función recursiva respectiva (sin validación) es:
El problema de invertir los dígitos de un número se resuelve tomando en cuenta que el número invertido es igual a su cociente entre 10, con sus dígitos invertidos, añadiendo su residuo entre 10 como primer dígito. Por ejemplo, si el número es 12345, el número invertido se obtiene con 4321+5*10000 = 54321, donde 4321 es el cociente ((12345-12345%10)/10=1234) con sus dígitos invertidos, 5 es el residuo (12345%10=5) y 10000 es el múltiplo de 10 con el mismo número de dígitos que el número a invertir. Cuando el número tiene sólo un dígito (cuando es menor a 10) el número invertido es ese número, siendo esa la condición base.
La función recursiva correspondiente (sin validación) es:
En este caso las operaciones se realizan en ambos sentidos: mientras se hacen las llamadas recursivas el número va dismininuyendo hasta que es menor a 10, luego, mientras se devuelven los resultados, se multiplica el residuo por "d", pero previamente "d" (que inicialmente es 1) se multiplica por 10, de manera que "d" es el múltiplo de 10 con el número de dígitos de "n" (en la última llamada recursiva "n" tiene 2 dígitos y "d" es 10, en la penúltima "n" tiene 3 dígitos y "d" es 100 y así sucesivamente).
Sin embargo, es importante comprender que los valores de "d" deben ser calculados después de que la función recursiva devuelve un resultado, porque si se calculan antes, en la última llamada recursiva "d" sería el múltiplo de 10 del número original y no del número con el que se hace la llamada, además, ese valor permanecería constante. Por esa razón, en este caso, la función recursiva tiene que ser programada dentro de otra función, donde la variable "d" inicia en 1 y es modificada dentro de la función recursiva.
En esta solución (como ejemplo) para que la función opere también con números negativos, antes de llamar a la función recursiva, se pregunta si el número es negativo y de ser así se llama a la función recursiva con el valor positivo (-n) y se cambia el signo del resultado (-inv), de esa manera, sin modificar la función recursiva, se obtienen los resultados correctos tanto para números positivos como para negativos.
La potencia entera "n" de un número real "x", calculada como se ha ejemplificado previamente, es muy ineficiente, así, para calcular 3.42500000 el algoritmo hace ¡2 millones quinientas mil llamadas recursivas!. Se logra un algoritmo más eficiente para calcular la potencia entera de un número real, tomando en cuenta que 3.42500000 es igual a:
| \[ 3.4^{2500000} = \left( 3.4^{1250000}\right)^2 \] |
Con lo que se reduce a la mitad el número de llamadas recursivas, reduciendo ¡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:
| \[ x^{2280} = \left( x\raisebox{0.9em}{$\frac{2280}{2}$}\right)^2 = \left(x ^{1140}\right)^2 \] |
Prosiguiendo de esa manera hasta que la potencia es 0 o 1, se tiene:
| \[ \begin{aligned} x^{1140} &= \left( x\raisebox{0.9em}{$\frac{1140}{2}$}\right)^2 = \left(x ^{570}\right)^2 \\[5mm] x^{570} &= \left( x\raisebox{0.9em}{$\frac{570}{2}$}\right)^2 = \left(x ^{285}\right)^2 \\[5mm] x^{285} &= \left( x\raisebox{0.9em}{$\frac{285-1}{2}$}\right)^2 \cdot x = \left(x ^{142}\right)^2\cdot x \\[5mm] x^{142} &= \left( x\raisebox{0.9em}{$\frac{142}{2}$}\right)^2 = \left(x ^{71}\right)^2 \\[5mm] x^{71} &= \left( x\raisebox{0.9em}{$\frac{71-1}{2}$}\right)^2 \cdot x = \left(x ^{35}\right)^2\cdot x \\[5mm] x^{35} &= \left( x\raisebox{0.9em}{$\frac{35-1}{2}$}\right)^2 \cdot x = \left(x ^{17}\right)^2\cdot x \\[5mm] x^{17} &= \left( x\raisebox{0.9em}{$\frac{17-1}{2}$}\right)^2 \cdot x = \left(x ^{8}\right)^2\cdot x \\[5mm] x^{8} &= \left( x\raisebox{0.9em}{$\frac{8}{2}$}\right)^2 = \left(x ^{4}\right)^2 \\[5mm] x^{4} &= \left( x\raisebox{0.9em}{$\frac{4}{2}$}\right)^2 = \left(x ^{2}\right)^2 \\[5mm] x^{2} &= \left( x\raisebox{0.9em}{$\frac{2}{2}$}\right)^2 = \left(x ^{1}\right)^2 \\[5mm] x^{1} &= \left( x\raisebox{0.9em}{$\frac{1-1}{2}$}\right)^2 = \left(x ^{0}\right)^2 \\[5mm] x^{0} &= 1 \end{aligned} \] |
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} \] |
Cuando la potencia es 0 (es menor a 1) el resultado es 1 (condición base).
La función recursiva correspondiente (sin validación) es:
Para calcular recursivamente el Fibonacci de un número entero positivo:
| \[ \begin{aligned} F_n &= F_{n-1}+F_{n-2}\\[2mm] F_1 &= 1\\[2mm] F_2 &= 1 \end{aligned} \] |
Dado que la definición del Fibonacci es una definición recursiva, se puede pensar en programar directamente la fórmula recursiva (fib = n => fib(n-1)+fib(n-2); ), pero, una expresión doblemente recursiva como esta, implica llamadas recursivas donde se calculan una y otra vez los mismos valores.
Por esa razón el número de llamadas recursivas incrementa geométricamente. Así para calcular el Fibonacci de 3 se requieren 2 llamadas recursivas, el de 18, 65536 llamadas recursivas (en lugar de 16) y el de 34, 4294967296 llamadas recursivas (en lugar de 32) ¡más de 4 mil millones de llamadas recursivas innecesarias!. Este es uno de los casos donde, a pesar de ser la definición recursiva, la solución es iterativa.
En estos casos (de forma similar a las sumatorias) se puede emplear la recursividad simplemente para lograr el número de iteraciones requeridas, siendo la lógica iterativa:
Los parámetros con valores por defecto se emplean de manera similar a las variables de una estructura iterativa: El contador "i" inicia en 3 (el primer Fibonacci que puede ser calculado) y su valor incrementa en uno en cada llamada recursiva. Las variables "f1", "f2" y "f3", se inician en los valores conocidos y en cada llamada recursiva se actualizan ("f1" toma el valor de "f2", "f2" el de "f3" y "f3" el nuevo valor del Fibonacci). El proceso concluye cuando el contador "i" es igual al número de Fibonacci "n" que se quiere calcular.
En la práctica para evitar la creación de nuevas variables en cada llamada recursiva, así como evitar mandar el mismo valor de "n" en cada llamada, debe ser programada dentro de otra función donde se declaran las variables una sola vez.
Para el cálculo de funciones matemáticas con series de Taylor, se pueden emplear también llamadas recursivas, no obstante (al igual que en el cálculo del Fibonacci) la solución tiene una lógica iterativa.
Por ejemplo, el seno de un ángulo "x" en radianes:
| \[ \sin(x) = x-\dfrac{x^3}{3!}+\dfrac{x^5}{5!}-\dfrac{x^7}{7!} +\cdots \infty \] |
Puede ser calculado con la siguiente función recursiva (sin validación):
Donde la función recibe el ángulo en radianes (x) así como las variables con los valores iniciales necesarios para el cálculo, luego, con esos valores se calcula el nuevo término (ter), la nueva sumatoria (s2) y si "s1" y "s2" son iguales en 14 dígitos se devuelve el resultado (s2), caso contrario la función se llama a sí misma con los nuevo valores del término (ter), la sumatoria (s2) y el contador (i+2) y se vuelve a mandar el ángulo (x) y el negativo del ángulo al cuadrado (xx=-x2) que son valores que no cambian.
Las llamadas recursivas se emplean simplemente para repetir el proceso y mandar los valores necesarios para la siguiente iteración. El resultado devuelto cuando se cumple la condición base, no se emplea en el cálculo, sino que simplemente es devuelve por cada una de las llamadas recursivas.
Una solución más eficiente (sin validación) se consigue programando la función recursiva dentro de otra función:
Finalmente, algunas funciones que son por definición recursivas y que pueden ser programadas directamente, como es el caso del Ackermann de dos números enteros "p" y "q":
| \[ a(p,q) = \begin{cases} q+1 &\text{si ~p=0}\\ a(p-1,1)&\text{si ~p>0 ~y ~q = 0}\\ a(p-1,a(p,q-1))&\text{si ~p>0 ~y ~q>0} \end{cases} \] |
Cuya función recursiva respectiva (sin validación) es:
Al ser doblemente recursiva, al igual que el Fibonacci, implica una lógica muy ineficiente, donde se calculan cientos, miles y millones de veces los mismos valores. No obstante, en este caso no existe una forma sencilla de reducir el número de llamadas recursivas, por lo que usualmente son programadas directamente (como se ha hecho en este ejemplo). Debido a ello, son útiles sólo para valores pequeños y en este caso, por ejemplo, no es posible calcular el Ackermann de (4, 1):
Si bien en los ejemplos y ejercicios de este y de los capítulos anteriores, se resuelven problemas relacionados al área de las matemáticas, la lógica involucrada es de utilidad práctica y aplicable en otros campos del área de la informática.