Recursividad en Java - ejercicios, ejemplos y teoría

En este post hablare sobre la recursividad en el lenguaje de programación Java. Al principio la recursividad puede ser algo complicada de entender, eso de que un método o función se llame dentro de si mismo a suena a locura.

En este post veremos ¿Qué es y como funciona la recursividad en Java? y al final veremos algunos ejercicios de practica y ejemplo para que logres entender de manera clara este concepto.

Que es la recursividad en Java?

Las funciones o métodos recursivos son aquellos que se invocan a si mismas en algún momento de su ejecución. En análisis de Algoritmos las técnicas recursivas se usan mucho para la solución de problemas particulares, los cuales serian muy difícil de resolver usando métodos tradicionales iterativos.

Esta forma en análisis de Algoritmos es llamada Divide y Vencerás. Para poder resolver un problema de forma recursiva es necesario saber alguna solución no recursiva para alguno de los casos mas sencillos, también se le suele llamar "caso base".

"Se usa la solución más simple para resolver un problema más complejo". De echo hay algoritmos de ordenamiento que usan la técnica de divide y vencerás para ser mas eficientes.

Así, todo método recursivo debe tener al menos una sentencia que devuelva un resultado (la solución del caso más sencillo o caso base) y las sentencias necesarias para acercarse en cada invocación a ese caso.

Caso base

En sentencia se le suele llamar caso base, el cual es un caso particular que nosotros conocemos la respuesta, luego a partir de ese caso base se construye la recursión.

Es importante aclarar que el calculo del caso base no debe ser recursivo.

Caso recursivo

La recursión permite programar algoritmos aparentemente complicados con un código simple y claro, ahorrando trabajo al programador.

Problemas de la recursividad

A simple vista parece la solución perfecta para muchos problemas, pero hay que tener en cuenta que en ocasiones ralentizará el programa en exceso y un mal algoritmo o función recursiva podría llevar a que se consuma toda tu memoria RAM destinada en el JVM (Java Virtual Machine).

Confieso que en todos mis cursos de programación, la recursividad fue uno de los temas que mas me costo trabajo entender, pero bueno, todo es disciplina.

Ejercicios y explicación de recursividad en Java

La recursividad no es una estructura de datos como muchos lo suelen confundir, sino que es una técnica de programación que nos permite que un bloque de instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas, ya que en casos particulares, la recursividad puede llegar a ser más eficiente. Este concepto será de gran utilidad para el capítulo de la estructura de datos tipo árbol.

La recursividad es un concepto difícil de entender en principio, pero luego de analizar diferentes problemas aparecen puntos comunes.

Recursividad en Java

En Java los métodos pueden llamarse a sí mismos. Si dentro de un método existe la llamada a sí mismo decimos que el método es recursivo.

¿Que pasa cuando un metodo se llama a si mismo?

Cuando un método o función se llama a sí mismo, se asigna espacio en la pila para las nuevas variables locales y parámetros. Al volver de una llamada recursiva, se recuperan de la pila las variables locales y los parámetros antiguos y la ejecución se reanuda en el punto de la llamada al método.

Ejemplos de recursividad en Java

Algoritmo recursivo para calcular el factorial de un numero.

int factorial(int n){
      if(n==0) return 1;   //AXIOMA
      else return n*factorial(n-1);  //FORMULA RECURSIVA
   }

Algoritmo recursivo que encuentre la serie fibonacci.

 int fibonaci(int n){
      if(n==1 || n==2) return 1;
      else return fibonaci(n-1)+fibonaci(n-2);
    }

Division de restas sucesivas en un algoritmo recursivo.

int division (int a, int b)
    {
	if(b > a) return 0;
	else
	    return division(a-b, b) + 1;
    }

Invertir un numero entero usando un algoritmo recursivo.

 int invertir (int n)
    {
	if (n < 10)         //caso base
	    return n;
	else
	    return (n % 10) + invertir (n / 10) * 10;
    }

Programar un algoritmo recursivo que permita sumar los dígitos de un número.

 int sumar_dig (int n)
    {
	if (n == 0)      //caso base
	    return n;
	else
	    return sumar_dig (n / 10) + (n % 10);
    }

Programar un algoritmo recursivo que permita hacer una multiplicación, utilizando el método Ruso.

 int mult_rusa(int A, int B)
    { 
        if(A==1){
	    return (B);
	}
	if(A%2!=0){
	return(B+mult_rusa( A/2 , B*2));
	}
	else{
	return(mult_rusa( A/2 , B*2));
	}                                
    }

Programar un algoritmo recursivo que calcule el Máximo común divisor de dos números.

    int sacar_mcd(int a, int b) {
        if(b==0)
            return a;
        else
            return sacar_mcd(b, a % b);
    }