Recursividad usando java

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.

Clic aqui para ver el codigo para hallar factorial iterativamente.

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

Aprendiendo a programar en java usando el valor de π(pi)

Saludos a todos.

Hace muchísimo tiempo cuando curioseaba el lenguaje Pascal y antes de dormir me puse a pesar en la geometría del circulo y recordé las clases de colegio donde me decían que el valor de pi no era mas que la longitud de la circunferencia dividida entre su diámetro.

Tenia presente que midiendo la circunferencia y el diámetro de un plato redondo por ejemplo solo hallaría un valor aproximado de pi, y que dicho valor más exacto sólo lo podían hacer los matemáticos y sus demostraciones, cosa que difícilmente lograría yo.

Siempre he sido regular en matemáticas, para algunos muy bueno, la verdad no lo creo; pero sí me consideraba mejor en la geometría y dibujo técnico.

De tanto pensar en círculos, matemática y geometría llego a mi una forma de hallar el valor de pi sin hacer demostraciones, gracias a que recordé que había leído en alguna parte la teoría que mas o menos dice "Un circulo es una figura geométrica con muchos lados que equidistan de un centro o eje"

Se me prendió el bombillo, me dije, tomare un cuadrado del cual conozco su diámetro y le agregare más lados calculado de los ya existentes sin cambiar el diámetro del mismo, es decir que el diámetro sera una constante; la suma de sus lados me darían el perímetro el cual dividiría por el diámetro y me daría el valor aproximado de pi, si hago esto muchas veces me acercaré cada vez más a pi; en otras palabras le agregare más lados al cuadrado tratando de convertirlo en un circulo.

Tome lápiz, cuaderno y comencé ha calcular, para el caso de un cuadrado de diámetro 1 los lados medirían 0,707106781, ya que según Pitágoras:

h^2 = co^2 + ca^2

Como para un cuadrado sus lados son igual, es decir sus catetos, nos quedaría:

h^2 = co^2 + co^2

h^2 = 2 * co^2

Sacamos raíces a ambos términos de cada igualdad

h = √2 * co

finalmente

co = h/√2

siendo la hipotenusa nuestro diámetro y remplazando...

co = 1/√2 = 0,707106781;

Listo ya tengo los datos de mi cuadrado, como los cuadrados tienen 4 lados el perímetro sería (0,707106781 * 4) = 2,828427125

Nuestro primer valor aproximado para pi seria:

2,828427125/1 = 2,828427125

2,828427125 es un valor muy distante al verdadero valor de pi; lo que sigue ahora es usando geometría agregarle más lados a figura y calcularlos sin cambiar el diámetro (1) y recalcular el valor de pi; en la practica debía recalcular miles de veces para llegar a un valor decente de pi.

Tome nuevamente mi cuaderno y lápiz, y escribir un programa en Pasca (en esa época no tenia computador, así que me tocaba a papel y compilar en mi cabeza) para luego esperar el sábado que tenia nuevamente contacto con un computador; para sorpresa mía el día que pase mi programa a computador funciono sin problemas dándome el valor de pi tal cual una calculadora, estaba muy excitado al llegar muy cerca al valor de pi sin ser matemático.

Como mencione al inicio, eso paso hace mucho tiempo; y hoy que empece a recordar me ha sido duro reconstruir el programa, sospecho que es por mi pereza de hacer algo dos veces, así que investigue algo que me ayudara a recordar y me tope conque ya eso lo habían hecho Arquimedes y lo llamó Método exhaustivo, aunque mi método es ligeramente distinto, así que más pereza me da reconstruirlo, pero en un futuro lo haré para ustedes.

Pero como es costumbre escribir código en cada una de mis entradas, me tope con la Fórmula de Leibniz que no es más que una sumatoria que tiende al infinito y que es fácil programar.

//Autor Rey Salcedo
class FormulaLeibniz{
 public static double formula(int repeticiones){
  double pi = 0;
  for(int n = 0;n < repeticiones;n++){
   pi += ((Math.pow(-1,n))/(2*n + 1));
  }
  return pi*4;
 }
 public static void main(String[] args){
  System.out.println(formula(100000000));
 }
} 

Espero le sirva y les sea de agrado