Un programa o sub-programa recursivo se llama a si mismo constantemente cada vez desde una situación más sencilla (o igual ala anterior) de manera que se llega a un problema final trivial y el proceso se detiene. Como dice Gary Cornell: "para un programador con experiencia el pensar de forma recursiva rpresenta la única alternativa a determinados problemas, produciendo a menudo, soluciones especialmente elegantes y por lo tanto programas elegantes".
La recursividad se utiliza con preferencia frente a otros métodos de programación en multitud de situaciones, como por ejemplo en resolución de problemas que conllevan el resolver muchos pasos idénticos en sucesión, cada uno de cuyos estadios depende del anterior en alguna forma (como por ejemplo el cálculo de un factorial que luego veremos). También es típico el uso de algoritmos recursivos cuando se tiene que recrear la estructura de directorios de una unidad (o de la memoria de la HP) o se debe hacer una búsqueda selectiva por un estructura de datos complicada como pueden ser algunas jerarquías....
La recursividad en un programa la podemos aplicar de manera directa (es decir un programa se llama a si mismo sucesivas veces de manera recursiva), o de manera indirecta (un programa llama a otro y éste último llama al primero y así sucesivamente). Además en la HP podemos definir mediante el uso de variables locales compiladas un subprograma dentro de uno principal mayor, de manera que se llame a si mismo sin salir del principal... Tranquilo/a ahora veremos un ejemplo de esto último.
Antes de comenzar a ver algún ejemplo, debo advertir que la recursividad es un concepto complicado aunque a simple vista pueda parecer lo contrario, y se debe tener un cuidado especial y una "visión de futuro" importantes cuando se plantea la resolución de un problema mediante la recursividad, ya que podemos entrar en un proceso infinito de llamadas de un proceso a si mismo de manera que al final nos quedemos sin memoria de usuario ( o más técnicamente "sin memoria de pila") y se nos cuelgue el sistema en el mejor de los casos. Lo que hay que hacer es asegurarse siempre que en cualquier situación que se nos plantee en mayor o menos tiempo deberemos asegurar que se va a llegar a un problema trivial y la situación recursiva se va a detener.
Para comenzar vamos a ver dos maneras de resolver el mismo problema: la tradicional y la recursiva.
El problema que planteo es hallar el factorial de un número cualquiera. No me voy a plantear nada más que ilustrar el concepto de recursión, y por lo tanto no entro en disquisiciones acerca de la manera de pedir datos (ver el texto de Mario al respecto en esta página) ni en la comprobación de errores o validez de argumentos (que sean números naturales, etc..).
La forma tradicional de resolver este problema sería el uso de un bucle que sin más fuese multiplicando los números entre el dado y 1 disminuyendo en la unidad el número dentro del bucle. Este programa tendría un aspecto tal que así:
<< DUP 1 - 1 FOR I
I *
-1 STEP
>>
Primero duplicamos el número en la pila para tener un argumento para la primera multiplicación que realicemos y después establecemos los límites del bucle de manera que dentro de este multipliquemos los números hasta el 1 por lo que haya en la pila (que será el resultado de las anteriores operaciones). De hecho aún se puede mejorar el programa haciendo que el bucle llegue sólo hasta el 2 y no hasta el 1 puesto que la última multiplicación por 1 es innecesaria y aumenta el tiempo de proceso.
Lo cierto es que este programa es extremadamente sencillo y en este caso no estará justificada el uso de la recursión, pues el programa no quedará tan claro (la recursión siempre es dificil de ver como trabaja). De todas formas en este planteamiento que yo califiqué de "tradicional" un programador experimentado puede ver fácilmente que ya se contempla el concepto de recursividad. Bien es cierto que no se llama a otro programa varias veces, pero como en la HP dejamos siempre argumentos en la pila, aquí el operador * del producto actúa casi como si fuese un rpgrama que llamamos de manera recursiva. Creo que me he explicado ¿No?..
Ahora veamos como se haría de manera recursiva, que aunque quede más complicado nos permitirá ver como se utiliza esta técnica.
Para ello veamos el siguiente listado:
Primero escribimos un pequeñísimo programa que se encarga de poner el primer argumento en la pila y de llamar acto seguido al recursivo "Factorial" que será el realmente encargado de hacer las operaciones
<< DUP Factorial >>
Ahora el encargado realmente de operar es "Factorial" :
<< 1 -
IF DUP 1 > THEN
DUP Factorial END
*
>>
que lo único que hace es restar uno al número que se le pasa como argumento y se llama a si mismo si no hemos llegado a 1 en esta resta. Después, cuando las subsiguientes instancias de si mismo terminan y devuleven el control al programa que las llamó (es decir nos ponemos en cada instancia justo después del END) se multiplican los números que hay en la pila sucesivamente, puesto que es la única operación que queda. Dicho de manera más llana: Son instancias del mismo programa que se contienen unas a otras y que no dejan continuar la ejecución de su "padre" hasta que ella misma y todas sus hijas no hayan terminado de ejecutarse...
En fin, aunque este ejemplo no es probablemente el más apropiado (de hecho la versión recursiva va más lenta que la tradicional) si ha servido para mostrar en poco espacio y con una tarea sencilla el concepto de recursión, que es lo que se buscaba.
Puesto que se pueden resolver problemas mucho más complicados que este con la Recursividad propongo al lector/ra el siguiente desafío:
Dado el nombre de una variable de la HP, hacer un programa que la busque por toda la memoria (por todos los directorios y subdirectorios) de manera que devuelva una lista con todos los lugares donde se ha localizado la variable. Yo lo he hecho con recursión embebida dentro del propio programa en una subrutina local (posibilidad que comento al principio de este texto) y no se me ocurre otra manera de hacerlo. Puedes bajarte el listado pulsando Aquí.
De todas maneras si a alguien se le ocurre otra forma de hacerlo sin utilizar la recursión aunque ni siquiera vaya más rápido que el mio, me gustaría que me lo hiciese saber.
Hasta entonces un saludo.