Share via

1. Recursion - Where are my for/while loops?

  • Article

 

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:

fact_wiki_it

 

or

 fact_wiki_rec

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:

image

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#:

 fact_cs_rec

We can notice that:

  • We don’t need the for loop anymore.
  • We don’t need side-effects (aka no assignment)
  • The function body is slightly shorter.
  • We don’t need an explicit accumulator variable to store the intermediate computation, instead the n parameter (allocated implicitly on the stack) is used to hold it.

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#:

fact_fs_rec

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:

  • The let keyword allows you to bind symbol/names to values. for example let pi = 3.14 will bind the value 3.14 to the name pi. Binding a value is different from assigning a value to a variable, since in functional languages you should not modify the value once it has been bound. Avoiding side effects is great, it protects us from a lot of bugs especially in a parallel environment. You don’t need to precise a type for the pi, like the Haskell compiler, the F# compiler is smart enough to infer it, F# float type in this case, which corresponds to C# double type. Values defined by let are visible in the let body, which is here visible thanks to its indentation, we speak about lexical scope.

  • The rec keyword specifies that this binding is recursive, so even if fact is not defined yet it will be visible in its lexical scope.

  • The function keywords allows to create a function which takes a single argument and does pattern matching on it (see my article on pattern matching for more information). It says that:

    • if the value of the function is 0 then the result should be 1
    • else if the value of the function is n then the result should be n * fact(n - 1)

 

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)

Comments

  • Anonymous
    January 09, 2012
    My favorite F# factorial: let inline factorial n = Seq.reduce (*) [ LanguagePrimitives.GenericOne .. n ] From: rosettacode.org/.../Factorial But along the same lines, here's an example of tail recursive forward passing: let fact x =  let rec factp =    function    | a, 1 -> a    | a, n -> factp (a * n, n - 1)  factp x;;

  • Anonymous
    January 09, 2012
    That "factp x" really should be factp (1, x) . Oops.

  • Anonymous
    January 09, 2012
    Hello @Rick Minerich: I will show it in my article on 1st class functions: With definition of map, filter, length, reverse, sum, product, ... in terms of foldl/foldr and then fact would be equivalent to your example with reduce: let fact n = product [1..n] But perhaps too much to start :)

  • Anonymous
    August 04, 2013
    great dude <a href='www.dotnetbull.com/.../factorial-program-recursion-while-for-loop.html& for factorial using recursion, while and for loop in c#</a>

  • Anonymous
    August 04, 2013
    Great dude : www.dotnetbull.com/.../factorial-program-recursion-while-for-loop.html