Saludos lectores, aunque éste tema está muy bien documentado en Internet, a continuación lo expongo de manera fácil y como de costumbre con código.
Definición: Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente (Por Wikipedia).
En pocas palabras, usamos recursividad cuando un método se llama a sí mismo para resolver un problema.
Expongo un método no muy común para darlo como ejemplo, pero fácil de entender:
public class recursividad{
private static int suma(int a,int b){
return a + b;
}
private static int suma(int a,int b,int c){
return suma(suma(a,b),c);
}
private static int suma(int a,int b,int c,int d){
return suma(suma(a,b),suma(c,d));
}
private static int suma(int a,int b,int c,int d, int e){
return suma(suma(a,b,c,d),e);
}
public static void main(String []args){
int a = 1;
int b = 3;
int c = 4;
int d = 5;
int e = 6;
System.out.println(suma(a,b));
System.out.println(suma(a,b,c));
System.out.println(suma(a,b,c,d));
System.out.println(suma(a,b,c,d,e));
}
}
El anterior código desde el punto de vista de algoritmo no es exactamente recursividad ya que éste codigo funciona gracias a una propiedad presente en Java llamada poliformismo; pero es un buen ejemplo de inicio para entender.
Si observamos el primer método suma que recibe por parámetros dos número enteros es el que hace la operación arismetica de la suma, los demás métodos suma se benefician de manera recursiva del primero.
Muchos problemas mátematicos se pueden resolver de manera recursiva, pero por lo general es el problema y nuestra forma de abordarlos lo que define si se puede o no resolver de manera recursiva.
Pasemos a un ejemplo más practico y usado para enseñar recursividad, hallar el factorial de un numero usando la recursividad en Java.
El factorial de un numero se define de la siguiente forma:
n! = 1 X 2 X 3 X 4 X ... X (n -1) X n
O de ésta otra forma más facil para nosotros: n! = 1 * 2 * 3 * 4 * ... * (n -1) * n
Para entender mejor miremos ejemplos y lo facil que es calculemos 5! que se lee factorial de 5.
5! = 1 * 2 * 3 * 4 * 5 = 120
Calculemos otros factoriales.
3! = 1 * 2 * 3 = 6
2! = 1 * 2 = 2
Surge una pregunta, cual es el factorial 0?, por definición el factorial de cero es uno, es decir ( 0! = 1 ), ¿Por que?, soy sincero, ésta respuesta la saben los matematicos y ellos la pueden explicar mejor que yo, con todo y demostración.
Antes de seguir hay algo muy importante al momento de hacer métodos recursivos, hay que tener un caso base; el caso base es el punto en el código donde acaba la recursividad, sin este caso base se generaría una recursividad infinita, más adelante mostraremos con ejemplo el caso base.
Sigamos calculando factoriales:
Ya sabemos que factorial de 5 es 1 * 2 * 3 * 4 * 5; pero podemos decir que es igual a (1 * 2 * 3 * 4) * 5; hasta aqui lo unico que hicimos fue agrupar (1 * 2 * 3 * 4) y multiplicarlo por 5; asi:
5! = 1 * 2 * 3 * 4 * 5 = (1 * 2 * 3 * 4) * 5 = 120
pero a que es igual (1 * 2 * 3 * 4) ?
(1 * 2 * 3 * 4) = 4!
Es decir que:
5! = 4! * 5
Si se fijan aqui ya hay recursividad, para hallar el factorial de 5 necesitamos hallar el factorial de 4.
Este orden de idea resolveremos el factorial de 5 paso a paso, y usando algo asi como una prueba de escritorio.
Factorial de 5?
5! = ?
Factorial de 5 es factorial de 4 por 5
5! = 4! * 5
Pero no se cual es el factorial de 4, facil, factorial de 4 es factorial de 3 por 4
4! = 3! * 4
Pero no se cual es el factorial de 3, facil, factorial de 3 es factorial de 2 por 3
3! = 2! * 3
Pero no se cual es el factorial de 2, facil, factorial de 2 es factorial de 1 por 2
2! = 1! * 2
Pero no se cual es el factorial de 1, facil, factorial de 1 es factorial de 0 por1
1! = 0! * 1
Pero yo si se cual es el factorial de 0, por definición 0! = 1; éste es nuestro caso base.
Ahora toca devolverse para ir resolviendo lo calculos que dejamos pendientes atras asi:
si: 0! = 1
y si: 1! = 0! * 1
entonces:
1! = 1 * 1 = 1
si: 1! = 1
y si: 2! = 1! * 2
entonces:
2¡ = 1 * 2 = 2
si: 2! = 2
y si: 3! = 2! * 3
entonces:
3¡ = 2 * 3 = 6
si: 3! = 6
y si: 4! = 3! * 4
entonces:
4¡ = 6 * 4 = 24
si: 4! = 24
y si: 5! = 4! * 5
entonces:
5¡ = 24 * 5 = 120
Cuando nos regresamos a resolver las operaciones que dejamos pendientes, nuestros computadores también lo hacen cuando resuelven algoritmos recursivos, dichas operaciones pendientes por resolver las almacenan en las llamadas pilas de procesos, es por esta razón que nuestros algoritmos recursivos exigen más de nuestros computadores que los algoritmos no recursivos.
Una cosa curiosa que ustedes han notado, es que hacer nuestras pruebas de escritorio de algoritmos recursivos resultan largos pero ironicamente las linea de código que usamos es menor vs no recursivos.
Como ya habiamos visto la forma de representar el factorial de un numero es:
n! = 1 * 2 * 3 * 4 * ... * (n -1) * n; ésta es la forma iterativa y se resumen en una sucesión de multiplicaciones que parten de uno y terminan hasta el numero que deseamos calcular.
Ahora miremos como representar el calculo de un número factorial usando recursividad:
n¡ = (n - 1)! * n
pero para tener encuenta el caso base para que no se nos valla la recursividad al infinito la definiremos mejor así:
Sin más preambulo, les comparto el sencillo código para calcular factorial de un número de manera recursiva.
public class factorial{
private static double factorial(int n){
if (n==0){//caso base
return 1;
}else{
return (factorial(n-1))*n;
}
}
public static void main(String []args){
System.out.print(factorial(5));
}
}
Otro problema que se puede resolver recursivamente es la sucesión de Fibonacci, el codigo ya lo hice en una entrada anterior, aquí te dejo el
link
Chao y exitos a todos
