Para entender la recursividad

Recordaba una vez en la que hice un shell script y se me ocurrió ver si podía hacerse recursivo. Sorprendentemente sí se pudo. Eso me permitió hacerlo más pequeño y sin tanta variable y banderas de control. Cada instancia del script se cuidaba a sí misma por tener un espacio propio y confinado de existencia. Algo de tiempo después de entregarlo un jefe enojado me mandaba llamar porque no entendía lo que el script hacía no cómo lograba hacerlo. Aunque ofrecí dar explicaciones y la documentación de soporte me pedían “hacer cosas mantenibles” y no complicadas. Algo de tiempo después llegué a tener otro jefe que acostumbraba decir “la miel no se hizo para los burros”. Creo que la frase aplica también al caso anterior.

Recursividad

Los últimos días me he topado con varios eventos o casos en los que la recursividad está presente, y no deja de maravillarme como de esta forma con tan poco se logra tanto. No he podido evitar recordar lo que ya he descrito.

La recursividad es el proceso de resolución de un problema en términos de versiones más pequeñas de sí mismo. Al hacerse más pequeño cada vez, se llega a cierta esencia (el “caso base”) que puede resolverse directamente. Para lograr esto uno debe asegurar tres cosas:

  1. Que el problema se haga más pequeño cada vez.
  2. Incluir una solución para el caso base.
  3. Manejar todos los casos que no sean el caso base de forma genérica.

Eso es realmente todo lo que hay que hacer.

Matrioska

Recordando aquella anécdota, ¿qué pasa con el entendimiento de  cómo se ejecuta el código? Realmente, a menos que uno sea un científico de computación tratando de estudiar la complejidad computacional del algoritmo, la verdad es que uno no tiene que hacerlo. Y ese es el punto: a veces una solución recursiva es más fácil precisamente porque no tiene que entenderse el detalle de su ejecución. Paul Graham explica en su libro “ANSI Common Lisp” qué trazar la ejecución no es realmente necesario:

Students learning about recursion are sometimes encouraged to trace all the invocations of a recursive function on a piece of paper. … This exercise could be misleading: a programmer defining a recursive function usually does not think explicitly about the sequence of invocations that results from calling it. … How do you visualize all those invocations? You don’t have to.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s