Tan recursivos pues!

El tema que me lleva hoy a escribir es la idea de recursión. Bueno, es uno de esos temas difíciles de explicar la primera vez y requiere algunas claridades frente a como funcionan las invocaciones a métodos.

¿Cómo funciona un método?

Cuando uno invoca un método, se "abre" espacio en la computadora para ejecutar un cierto conjunto de instrucciones (el contenido del método). Cuando se realizan muchas invocaciones, mucha memoria RAM del computador está siendo usada para ello. En una versión gráfica, es como si creáramos una caja que nos resuelve un problema dadas unas entradas y asegurando unas salidas.

              +-----------------------+
              |     Metodo!           |
         .    |                       |      .
   ........   |                       |   .....
   Entradas   |                       |  Salidas
              |                       |
              |                       |
              +-----------------------+

De esta manera, un método que tiene la responsabilidad de sumar dos números recibiría (entrada) como entrada dos elementos del conjunto de número enteros y devolvería (salida) un elemento del conjunto de números enteros. Para resolver dicha operación se crearía una "caja" simple que resolvería esa operación.

Cuando un método llama otro método, se abren varias "cajas" que esperan resultados unas de las otras, recordemos que un método tiene una responsabilidad definida. Cuando la resolución de un problema es compleja, se debe romper el problema en partes más sencillas, así mismo cuando un método se está complicando, es importante partirlo en métodos más simples. Cuando un método llama a otro, se crea algo llamado "pila de llamados".

  
  +---------+
  | Jugar   |
  +---------+
  | Menu    |
  +---------+
  | Main    |
  +---------+

La anterior pila de llamados representa un programa que inició con un llamado al método Main (como todo programa en Java), a su vez este llamó a un método que se llama Menú y a su vez este llamó a un método que se llama Jugar. En este momento la pila de llamados tiene en su punta el método jugar, que posiblemente es el que está ejecutando. Cuando este método termine, el método menú recibirá su respuesta y así pasará cuando termine el método Menú. Cada método tiene su espacio para guardar cosas, entre ellas las variables que se declaran dentro de él, sus parámetros y demás cosas.

Ahora sí, a lo que vinimos

Resulta que una recursión es un llamado de un método a sí mismo para la resolución sucesiva de un problema. En términos de la pila de llamados, se generarían espacios del mismo método. Supongamos una función que simplemente se llama a sí misma:

public static int metodo(int parametro)
{
   return metodo(parametro+1);
}

Resulta que el método de nuestro ejemplo crearía un número infinitos de entradas en la pila de llamados (teóricamente, porque en la práctica esa pila tiene límites y al sobrepasarlos se genera un error llamado StackOverflow o volcado de pila). Esto se vería más o menos así: (si el primer llamado fúe metodo(1))

     ...
 +---------+
 |metodo(3)|
 +---------+
 |metodo(2)|
 +---------+
 |metodo(1)|
 +---------+

Resulta que el llamado metodo(1) está esperando que el llamado metodo(2) termine, al igual que este último espera por metodo(3) y metodo(3) por metodo(4) y así sucesivamente. Respecto al ejemplo de Main->Menú->Jugar no cambia mucho, excepto por el hecho de que todas las componentes de la pila tienen el mismo nombre. En el código de ejemplo, estos llamados nunca terminarán porque siempre se genera un llamado nuevo. Esto resultará en un StackOverflow... Para detenerlo necesitamos un caso donde no se hagan llamados recursivos, a esto lo llamaremos posteriormente un caso base. Modifiquemos el código del anterior ejemplo para que eso pase cuando el parámetro llegue a un cierto valor, por ejemplo M.

public static int metodo(int parametro)
{
    if(parametro == M)  
    {
        return 0;
    } 
    return metodo(parametro+1);
}

En ese caso los llamados recursivos se expanderían hasta que el valor de la variable parametro llegue a M, cuando llegue, se retornará cero a todos los métodos anteriores. Aunque este método ya no tiene un StackOverflow, es un método sin mayor utilidad, pero revisemos el siguiente:

public static int factorial(int parametro)
{
   if(n==1)
    {
        return 1;
    }
    else
    {
        return parametro* factorial(parametro-1);
    }
}

En este ultimo caso, tenemos un caso en que se detiene (cuando n sea 1) y uno donde expande el llamado (n diferente de 1). De esta manera tenemos un caso base y un caso inductivo. Espero les sirva!