Most imperative programmers who start learning functional programming are lost because they don’t see loop constructs in code. Indeed even if some functional languages such as F# provide looping constructs they rarely or sometimes never use them. Why? Because actually they are not necessary, we can get ride of them thanks to a powerful concept: recursion. We say that a function is recursive when it calls itself within its body.
Let’s have a look at an example using the famous factorial function defined by:
The definition on the left is iterative, factorial (!) is defined by a product. The definition on the right is recursive, n! = (n x (n – 1)!) since the function factorial (!) appears before and after the symbol (=).
The C# code below shows how you could implement this function iteratively using a for loop construct:
This function is using an accumulator to store the intermediate computation during each iteration.
Let’s see how you could have implement this recursively in C#:
We can notice that:
It seems that recursion is more clear and concise so why don’t we use it in C# instead of loops like in functional programming languages?
The answer is simple, developers should not assume that C# as most other imperative languages (C, C++, …) is optimized for recursion. When a function is called it allocates a block of memory called a frame on the stack to store its local variables and return address (if not stored in a register), nested function calls cause the frames to pile up on the stack. If too many nested calls occur, which is likely to happen with some kind of recursion, the stack gets out of memory and the program crashes. Most functional programming languages implementations optimize the recursion process. One type of recursion can be easily optimized, it occurs when a function returns with its own call, we say that the function is tail recursive. An optimized tail recursion has the same performances than a looping construct.
So what about non tail recursive calls? Isn’t it better to use a loop then?
All non tail recursive calls can be converted to tail recursive calls either explicitly or implicitly (through the language implementation) by using a transformation known as “Continuation Passing Style” (CPS)
So the first iterative factorial definition is better in the case of C#.
Below a way of implementing it recursively in F#:
Look how it is concise and clear! It looks like the mathematical definition! You will notice that this function is not tail recursive, indeed the last operation to happen in the second branch is not a direct call to fact, but a call to the multiplication operator (*) with arguments n and fact(n – 1). (see my article on 1st Class Functions to know how to make this function tail recursive)
About the syntax:
F# has a for and while construct, but you will rarely use them, since recursion should be preferred, however they are useful in some cases, when generating sequences for example (see my article on Sequences for more information)