Hora de recursividad🔗

La recursividad es uno de esos temas en la programación que viven bajo la idea de ser “difícil”, “de poca útilidad” y “misterioso”. De tal manera que uno suele encontrarlo envuelto en detalles de la propia computadora, evitando así integrarlo a nuestro razonamiento cotidiano al momento de programar.

Es lo que es🔗

De entrada, el concepto importante es Autorreferencia:

Wikipedia

En filosofía, también se refiere a la habilidad de un sujeto para hablar o referirse a sí mismo.

Ahora bien, ¿qué requiere un sujeto para hablar a si mismo?. Lo primero sería tener un nombre y lo segundo sería tener instrucciones para hablar a si mismo. Aunque aquí lo interpretaré como llamar a si mismo.

Suponiendo que se tiene a un niñito al cual se ha dado el nombre de Finn y la siguiente instrucción: cada vez que alguien te hable y te diga “Hola” seguido de tu nombre, responderás con “Hola” seguido del nombre de quien te ha hablado. ¿Qué pasa si Finn se habla a si mismo?:

  • Finn dice: Hola Finn
  • Finn piensa: me han hablado con “Hola Finn”, responderé.
  • Finn dice: Hola Finn
  • Finn piensa: me han hablado con “Hola Finn”, responderé.
  • Finn dice: Hola Finn
  • Finn piensa: me han hablado con “Hola Finn”, responderé.
  • Finn dice: Hola Finn
  • Finn piensa: me han hablado con “Hola Finn”, responderé.
  • ∞

Finn ha entrado en un ciclo infinito (∞) de llamadas a si mismo por seguir las instrucciones.

Hasta aquí es todo lo que implica el concepto de autoreferencia y por consiguiente de recursividad. Eso es la recursividad.

Sin embargo🔗

Se le puede dar la siguiente instrucción a Finn: solo responderás una vez con “Hola”, seguido del nombre de quien te ha hablado, cuando te digan “Hola” seguido de tu nombre. ¿Qué pasa si Finn se habla a si mismo?:

  • Finn dice: Hola Finn
  • Finn piensa: me han llamado con “Hola Finn”, responderé.
  • Finn dice: Hola Finn
  • Finn piensa: ya van más de una vez que Finn me ha llamado, ya no le responderé.

Finn ha evitado entrar en un ciclo infinito (∞) al tener mejores instrucciones.

Cuando ya no solo se trata de uno mismo🔗

Introduzcamos ahora a un perrito al cual se le ha dado el nombre de Jake y la siguiente instrucción: cada vez que alguien te hable y diga “Hola” seguido de tu nombre, responderás con “Hola” seguido del nombre de quien te ha hablado. ¿Qué pasa si Finn y Jake siguen la misma instrucción?.

  • Finn dice: Hola Jake
  • Jake piensa: me han llamado con “Hola Jake”, responderé.
  • Jake dice: Hola Finn
  • Finn piensa: me han llamado con “Hola Finn”, responderé.
  • Finn dice: Hola Jake
  • Jake piensa: me han llamado con “Hola Jake”, responderé.
  • Jake dice: Hola Finn
  • Finn piensa: me han llamado con “Hola Finn”, responderé.
  • Finn dice: Hola Jake
  • Jake piensa: me han llamado con “Hola Jake”, responderé.
  • Jake dice: Hola Finn
  • Finn piensa: me han llamado con “Hola Finn”, responderé.
  • ∞

Finn y Jake han entrado en un ciclo infinito (∞) de llamadas de uno al otro. A esto se le conoce como recursión mutua.

Hora de programar🔗

En programación el tema de la recursividad está envuelto por detalles propios de la computadora (John von Neumann):

  • Hardware: unidad de almacenamiento y unidad de procesamiento.
  • Software: lenguaje de programación, compilador, interprete, paradigma de programación, sistema de tipos, complejidad algorítmica, etc.

Usualmente se suele plantear a la recursividad en términos de un procedimiento, método o una función, sin embargo hay que tomar en cuenta su presencia en otros ámbitos de la programación.

Partiendo del siguiente código en Java:

public class Recursividad {
  public static int Finn(int n, int x, int y) {
    System.out.println("Finn(" + n + ", " + x + ", " + y + ")");
    return Finn(n, x + 1, y * (x + 1));
  }
  public static void main(String[] args) {
    System.out.println("main() := " + Finn(5, 0, 1));
  }
}

Se le ha dado a Finn la instrucción: cuando alguien te de 3 números, te llamarás a ti mismo con el primero número sin modificación alguna, el segundo número incrementado en uno y el tercer número lo multiplicarás por el segundo número incrementado en uno:

Al momento de ejecutarlo se obtiene lo siguiente:

Finn(5, 0, 1)
Finn(5, 1, 1)
Finn(5, 2, 2)
Finn(5, 3, 6)
Finn(5, 4, 24)
Finn(5, 5, 120)
Finn(5, 6, 720)
Finn(5, 7, 5040)
Finn(5, 8, 40320)
Finn(5, 9, 362880)
Finn(5, 10, 3628800)
...
Exception in thread "main" java.lang.StackOverflowError
...
at recursividad.Recursividad.Finn(Recursividad.java:5)
at recursividad.Recursividad.Finn(Recursividad.java:6)
at recursividad.Recursividad.Finn(Recursividad.java:6)
at recursividad.Recursividad.Finn(Recursividad.java:6)
∞

Finn ha entrado una vez más en un ciclo infinito (∞) de llamadas a si mismo por seguir nuestra instrucción.

Es hasta aquí que aparece algo que no existe en el concepto de recursividad: Stack y StackOverFlow. Ambos temas creo que oscurecen más el abordar la recursividad.

Sin prestar atención al Stack o al StackOverFlow se le puede dar una mejor instrucción a Finn:

public class Recursividad {
  public static int Finn(int n, int x, int y) {
    System.out.println("Finn(" + n + ", " + x + ", " + y + ")");
    if (x == n) {
      return y;
    }
    return Finn(n, x + 1, y * (x + 1));
  }
  public static void main(String[] args) {
    System.out.println("main() := " + Finn(5, 0, 1));
  }
}

Preguntas:

  • ¿Cuál es el objetivo final de lo que hace Finn? Sí, es la obtención del factorial de un número.
  • ¿Qué papel juega la condicional (if (x == n)) en Finn?
  • ¿Qué instrucción, en español, podría darse a Finn para expresar lo mismo que hace el último código de Java?

  • ¿Qué pasa si main(String[] args) llama a Finn de las siguientes maneras?:

    • Finn(8, 0, 1)
    • Finn(0, 0, 1)
    • Finn(-5, 0, 1)
    • Finn(5, 0, 100)
    • Finn(5, 100, 1)

Hora de recordar🔗

Pero antes de terminar, ¿existe la recursividad en el siguiendo código de Java? Sí, también es la obtención del factorial de un número.:

public class Recursividad {
  public static int Finn(int n) {
    System.out.println("Finn(" + n + ")");
    if (n == 0 || n == 1) {
      return 1;
    }
    return n * Finn(n - 1);
  }
  public static void main(String[] args) {
    System.out.println("main() := " + Finn(5));
  }
}

Su ejecución:

Finn(5)
Finn(4)
Finn(3)
Finn(2)
Finn(1)
main() := 120

¿Y en este otro? Sí, es la suma de los números en un arreglo.:

public class Recursividad {
  public static int Finn(int[] xs, int i, int y) {
    if (i == xs.length) {
      return y;
    }
    return Finn(xs, i + 1, y + xs[i]);
  }
  public static void main(String[] args) {
    System.out.println("main() := " + Finn(new int[]{10, 2, 30, 4, 50}, 0, 0));
  }
}

Su ejecución:

main() := 96

En conclusión🔗

La recursividad en si misma no tiene nada que ver con stacks (pilas), stack overflows (desbordamientos de buffer), ni mucho menos con casos bases, condicionales y la idea de “detener la recursividad”. Una vez más, la recursividad es lo que es.

Parte del porque se abordan los puntos anteriormente mencionados surge por querer entender la implementación dentro de la computadora (John von Neumann): los detalles de hardware y software… o mejor dicho sus límites. Por lo tanto considero que uno debería separar la noción de la implementación dentro de la propia computadora (el como) del de la definición de la recursividad (el que) para integrarlo a nuestro día a día.

Fuentes:🔗