Programación en Java/Funciones recursivas

Las funciones recursivas son aquellas 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. Esta forma en analisis de Algoritmos es llamada Divide y Venceras.

Para poder resolver un problema de forma recursiva es necesario saber alguna solucion no recursiva para alguno de los casos mas sencillos. "Usamos la solucion más simple para resolver un problema más complejo."

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

La recursión permite programar algoritmos aparentemente complicados con un código simple y claro, ahorrando trabajo al programador. 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. Por ejemplo, la función factorial en forma recursiva:

public class Factoriales {
     static int factorial(int numero){
          if ( numero <= 1 ) {
              return 1;
          } else {
              return numero*factorial(numero-1);
          }
     }
     public static void main(String args[]){
         System.out.println(factorial(5));
     }
 }

La misma función en forma iterativa:

public class Factoriales{
     static int factorial(int numero){
          int resultado = 1;
          while(numero > 0){
            resultado = resultado*numero;
            número--;
          }
     }
     public static void main(String args[]){
         System.out.println(factorial(5));
     }
 }

Como puede observarse, la función iterativa sólo recorre un bucle while, mientras que la recursiva invoca un método nuevo hasta que número vale 1 (Esto requiere un trabajo considerablemente mayor por parte del ordenador).

La recursión es por lo tanto una potente herramienta en programación, pero hay que saber diferenciar cuando es útil y cuando no.

Recursión mutua

Este en un ejemplo de recursión mutua. Se trata de un programa que devolverá true o false si el parámetro número es respectivamente, impar o par (en el caso de que invoquemos la función impar(número)).

public class Paridad{
 public static boolean impar (int numero){
     if (numero==0)
      return false;
     else
      return par(numero-1);
 }

 public static boolean par (int numero){
     if (numero==0)
      return true;
     else
      return impar(numero-1);
 }
}

Al leer el código de una sola de las funciones, no se aprecia la recursión pero existe igualmente. La recursividad es una técnica que puede utilizarse en lugar de la iteración para resolver determinados tipos de problemas.

FUENTE: Aprende a programar java desde cero

       Enrique García Hernández
       2012 España