Recursividad en Java

La recursividad en Java, como en la mayor铆a de lenguajes se realiza llamando al propio m茅todo o funci贸n donde nos encontremos.

La recursividad es una t茅cnica de programaci贸n muy utilizada para resolver problemas con un alto grado de complejidad. Dicha t茅cnica se basa en resolver un problema mediante recursi贸n, es decir, la soluci贸n final depende de las soluciones parciales del mismo problema. Algunas t茅cnicas muy utilizadas son las siguientes: «Divide y Vencer谩s» o «Backtracking» emplean la recursividad como modo de resoluci贸n.

En resumen, la mayor铆a de los lenguajes de programaci贸n dan soporte a la recursi贸n, permitiendo a una funci贸n llamarse a s铆 misma mediante el texto del programa. Los ejemplos expuestos, a continuaci贸n, han sido codificados en java.

ALGORITMOS RECURSIVOS

Un algoritmo recursivo es un algoritmo que expresa la soluci贸n a un problema llam谩ndose a s铆 mismo.

Generalmente, las primeras llamadas al subprograma son de una complejidad muy grande y el objetivo es ir reduciendo dicha complejidad hasta que se llegue a una soluci贸n, para que se pueda manejar iterativamente. Por lo tanto, llegar a este resultado se conoce como caso base.

Para realizar un algoritmo recursivo se debe definir el caso base con su soluci贸n, cuando no se pueda resolver mediante el caso base se define la resoluci贸n recursiva que tiene como objetivo llegar al caso anterior.

A grandes rasgos el funcionamiento es similar al de una pila:

  • Se crea una pila que contendr谩 la operaci贸n recursiva.
  • Cada nueva llamada apila la nueva soluci贸n parcial
  • El fin de cada llamada desapila y recupera el valor de la llamada anterior y as铆 sucesivamente.

EJEMPLOS DE RECURSIVIDAD EN JAVA

  • Suma n煤meros pares positivos hasta un n煤mero obtenido:聽el algoritmo suma todos los n煤meros pares positivos desde el 0 hasta n.
    public static int suma(int n)
    {
        if (n <= 0)
            return n;
        else if (n % 2 != 0)
            return suma(n - 1);
        else
            return n + suma(n - 1);
    }

    La pila resultante de la operaci贸n anterior es la siguiente:

     

    [ suma(0) , 2+suma(1), suma(2), 4+suma(3) ]

    Se puede apreciar c贸mo se van realizando las diferentes llamadas, dependiendo si el n煤mero es par o no. Una vez calculado que el valor de 鈥渘鈥 es 鈥0鈥 (Caso base), se procede a desenrollar la pila tomando todas las soluciones parciales, para as铆 llegar a la soluci贸n final.

  • Factorial de un n煤mero: consiste en multiplicar n por todos los n煤meros anteriores a 茅l hasta el 1.
    public static int factorial(int n)
    {
        if (n <= 1)
            return n;
        else
            return n * factorial(n - 1);
    }

    El caso base es en 鈥1鈥 porque es cuando se puede dar soluci贸n al problema tomando las soluciones/medidas parciales con las que se iba reduciendo la complejidad. De este modo, tambi茅n est谩 contemplado para cuando es menor que 鈥1鈥, porque en el caso de introducir por ejemplo el 鈥0鈥 se debe devolver el n煤mero en cuesti贸n.

  • Exponencial de un n煤mero: el exponente de un n煤mero consiste en multiplicar ese n煤mero consigo mismo las veces que indica un exponente, as铆 con este algoritmo programaremos esa operaci贸n de manera recursiva, en el cual 鈥n鈥 representa el n煤mero y 鈥e鈥 el exponente.
    public static int exponencial(int n, int e)
    {
        if (e == 0)
            return 1;
        else if (e == 1)
            return n;
        else
            return n * exponencial(n, e - 1);
    }

    En este caso tenemos dos casos base para representar correctamente la soluci贸n final. Al igual que en los ejemplos anteriores se parte de un t茅rmino complejo y se va aminorando hasta llegar al caso base.

En definitiva, este tipo de programaci贸n es muy compleja y abstracta y la mejor manera de entenderla y aplicarla es llev谩ndola a la pr谩ctica, para que as铆 resulte m谩s f谩cil realizar dichos procedimientos.

 

curso programaci贸n en java

2 comentarios en “Recursividad en Java”

  1. Excelente el espacio y el tema de recursividad.

    Necesito de su ayuda, para saber como realizo la lectura de un archivo ascii de un programa en java donde en la misma linea de ejecucion el usuario indique cual es el archivo que desea leer. Por ejemplo:

    c:\>java Lector soucion.txt

    Mucho agradezco mucho su ayuda.

    • Muchas gracias!

      Lo primero que necesitas es saber como funcionan los argumentos en java y despu茅s realizar la lectura con alguna librer铆a de java.

      Si quieres puedo hacer un art铆culo sobre ello esta semana.

Deja un comentario