Until now, I was not faced with a problem for which recursion is the most natural solution. A couple of days go, when I was writing this program to test for a palindromic number, a recursive implementation seemed the most sensible approach. LiveScript being my new found love, I fired up vim, and… blank.
function fib x if x<0 then throw new Error if x<3 then x else fib(x-1)+fib(x-2)
require! 'prelude-ls'.fix fib = fix (fib) -> (x) -> if x < 0 throw new Error if x < 3 then x else fib(x-1) + fib(x-2)
Looks similar? Nope. Here, fix takes a function that returns a function as an argument, and returns a function that is the inner function, with the outer argument referring to the inner function itself. Did that make any sense? 😀
The beauty of this approach is that the function fib doesn’t get hoisted, it is just an ordinary variable assignment, not a named function, and we just did anonymous recursion!
Don’t know if the sound of it excites you, but I sure am excited. Recursion in an anonymous function? Isn’t that cool?
Actually, looks like one of the common applications of Y combinator is to do anonymous recursion, but I didn’t think of it earlier.