La recursión es una forma de resolver problemas típicamente asociada a los lenguajes de programación funcionales, donde en ocasiones se carece de estructuras tipo bucle. La idea de la recursión se fundamenta en resolver un problema mediante pequeñas instancias del mismo problema.
En FSharp, dada la herencia de OCAML y la utilización del algoritmo de inferencia Hindley-Milner, se utiliza la palabra reservada rec para definir una función recursiva.
Aquí un ejemplo de función recursiva:
let rec count n =
if n = 1000000 then
printfn «done»
else
if n % 1000 = 0 then
printfn «n: %i» n
count (n + 1)
()
La función anterior muestra por pantalla los múltiplos de mil y cuando ha terminado escribe el mensaje ‘done’.
Sin embargo, si tratamos de ejecutar el código anterior obtendremos una excepción indicando un desbordamiento de pila, pero entonces, ¿cómo podemos definir la función anterior de forma que no desbordemos la pila? Algunos compiladores, como el de FSharp, poseen una característica denominada Tail Recursion o recursión de cola que nos permitirá evitar el desbordamiento grabando en la pila la posición de retorno, así cuando continue lo hará directamente en dicha posición.
El problema que tenía la anterior función es que la última instrucción en ejecutarse, el retorno de la unidad, en realidad crea una operación diferida. La idea es básicamente que la última operación sea la llamada recursiva. Nuestra función recursiva de cola quedaría así:
let rec tailCount n =
if n = 1000000 then
printfn «done»
else
if n % 1000 = 0 then
printfn «n: %i» n
tailCount (n + 1)
Ahora sí, si la ejecutamos no tendremos desbordamiento de pila. El compilador se encargará automáticamente de optimizar la función y a efectos prácticos será igual que un loop. No tratéis de hacer esto en CSharp, porque al menos en la versión actual, no soporta tail recursion.
Edit: @gulnor comenta en twitter que en algunas situaciones excepcionales el compilador de CSharp sí hace Tail Recursion. Aquí un hilo algo más detallado: https://roslyn.codeplex.com/discussions/545455
Comentarios recientes