[F#] Tail Recursion y el Stack

En la entrada anterior veíamos cómo, de manera sencilla, podíamos razonar y entender las funciones recursivas. Pero ¿Cómo funcionan estas llamadas recursivas en .NET?

Empecemos por aclarar algo. Cuando se llama a una función, el computador debe recordar el lugar desde donde fue llamada, la dirección de retorno, de modo que pueda volver a ese lugar con el resultado una vez la llamada se ha completado¹. Estas direcciones son almacenadas en el call stack. Una vez la función retorna un valor la pila de llamadas se borra y el programa continúa desde la función llamadora.

Si una función recursiva se llama a si misma una y otra vez, como un loop, el stack se irá llenando con dichas direcciones (las llamadas a si mismo). El problema es que el stack no es infinito y podemos recibir una conocida excepción, si, la Stack Overflow Exception.

Podemos comprobar este comportamiento si escribimos una función que calcule el factorial de un número de manera recursiva, algo de la forma:

    let rec factorial =
        function
        | x when x > 1 -> x * factorial (x-1)
        | _ -> 1

Usando Visual Studio, podemos poner un breakpoint en el otherwise, donde esta el “1“, llamar la función y ver que pasa:

factorial

Ahora podemos probar calculando el factorial de Int32.MaxValue y ver que pasa… Process is terminated due to StackOverflowException.

Entonces, ¿Es posible escribir funciones recursivas que no llenen el call stack? La respuesta es si, y es lo que llamamos tail recursion (lo dejo en inglés porque recursión de cola no me gusta). Este tipo de recursión se basa en que todas las llamadas recursivas aplicarán la optimización de tail call. Esta optimización la obtenemos cuando la función llamadora retorna directamente el valor de la función llamada sin aplicar ninguna transformación/operación/reducción sobre dicho valor de retorno. Entonces, si todas las llamadas de la función recursiva son tail calls tendremos tail call recursion.

¿Pero cómo podemos lograr esto? Si analizamos de nuevo el tail call la respuesta pasa por retornar directamente la llamada a la función sin aplicar la función x*. Pero… ¿Y por cual valor multiplicamos? pues tendremos que usar un valor inicial (seed/acumulador/…). Con lo que la función factorial, tail recursive, puede ser definida así:

    let factorial' =
        let rec fact acc = 
            function
            | x when x > 1 -> fact (acc*x) (x-1)
            | _ -> 1
        fact 1

Cómo podemos ver ahora hay una nueva función dentro de la definición de factorial'. Esta función recibirá el valor del acumulador, que será 1 y el parámetro n. Si ponemos nuevamente un breakpoint en el otherwise, donde está el “acc“. Y usamos la función con Int32.MaxValue, esta vez veremos un call stack como el siguiente:

factorial1

De esta forma retornamos directamente la función sin hacer ninguna operación (x*) sobre la función.

En lenguajes funcionales, como F#, es común que el compilador optimice este código, y lo convierta a loops cómo los que tendríamos en lenguajes imperativos, logrando así el mismo comportamiento y performance.

Por el contrario, si queremos aplicar esta tipo de recursión en lenguajes como C# veremos que no hay ninguna optimización y el call stack se irá llenando con cada llamada a la función. El por qué en C# no se hace esta optimización es un misterio para mi, pero para eso esta F#.

Espero les sea de utilidad.

Hasta el próximo post.

Referencias

¹ Véase Wikipedia, Tail call, consultado: 7/11/2015.

MSDN Blog, Tail calls in F#

MSDN Blog, Understanding Tail Recursion

StackOverflow, Why doesn’t .NET/C# optimize for tail-call recursion?

Anuncios
[F#] Tail Recursion y el Stack

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