Is recursion good?

In today’s post I’m going to write a little bit about recursion. This text is aimed at programmers familiar with structural and object-oriented programming in languages like C/C++ or Java. I’m going to briefly summarize what recursion is, what happens when a recursive function is called, then I’ll explain what is proper tail recursion, tail call optimization and how to convert normal recursion into proper tail recursion using accumulator. Ready? Then let’s begin.

A brief overview

“Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem” – that’s what Wikipedia says. The easiest example is the definition of a factorial:

factorial 0 = 1
factorial n = n * factorial (n - 1)

This means that factorial of 0 is 1 (this is called a base case, which must exist in order to prevent infinite recursion), and factorial of 3 is 3 * factorial 2, which is 3 * 2 * factorial 1, which is 3 * 2 * 1 * factorial 0, which is 3 * 2 * 1 * 1 which is 6. The above code is also a valid Haskell program. Many problems in computer science are recursive by nature. Although every recursive algorithm can be converted into an iterative one – otherwise it wouldn’t be possible to perform recursion on sequential computers like the ones we have today – it often turn out that the recursive algorithm is much easier to write and understand1. Nevertheless, recursive definitions are often considered bad. Why? Let’s take a look at factorial definition in C:

int factorial( int n ) {
  if ( n == 0 ) return 1;
  return n * factorial( n - 1 );
}

When a recursive call is made – in fact when any function call is made –  a new stack frame is created. Stack frame contains copies of arguments passed to function, return address of the procedure and local variables of a function. Creating a stack frame takes a bit of time and if there are many recursive calls there is a risk of overflowing the stack. There are other risk as well, e.g. unnecessary recalculation of some values as in the case of Fibonacci sequence. Many programmers therefore consider that it is better to avoid recursive algorithms and replace them with iterative ones even if they are harder to write and understand. Looking from a Java or C/C++ point of view this might be the right thinking. But what if we could avoid creating a stack frame during the recursive call? Well, sometimes we can.

Proper tail recursion

Let’s rewrite our factorial function in C:

int factorial( int n ) {
  if ( n == 0 ) return 1;
  int temp = factorial( n - 1 );
  return n * temp;
}

Recursive call is made somewhere in the middle of a function. The result from this call is then used to perform more computations and produce a new result. This is called “body recursion”. Now consider something like this:

int print_loop( int n ) {
  if ( n == 0 ) return 0;
  int m = 2 * n;
  printf( "i%\n", m );
  return print_loop( n - 1 );
}

This function prints a decreasing sequence of even numbers from 2n to 2 (inclusive) and then returns 0. In this example when we reach the stopping condition (i.e. n == 0) we return a result. This result is then returned by the recursive functions without further processing. It means that recursive call is the last thing that is done within a function and when that call returns, the calling function itself will also return immediately. We call this “tail recursion”. When a function returns, its stack frame is removed. The return address from that frame is used to jump to the original calling point and since the return is the last thing we do in a tail recursive function this means that the remaining elements in the stack (arguments, locals) are discarded. Therefore, the call stack that we build is mostly useless – the only thing we need is the return address which is used only to get back to another return address. This can be optimized. In properly tail recursive function, instead of creating new stack frame when making a call, we can overwrite existing stack frame: replace old copies of arguments with the new ones, old local variables will be reused and the original return address is kept. This is called “tail call optimization” or “tail call elimination”.

Tail recursion using accumulator

As we’ve seen, our factorial definition isn’t tail recursive. Luckily, there is a technique that allows us to convert body recursion into tail recursion. It is based on using additional parameter – called the accumulator – that accumulates the result of calculations. Let’s rewrite our C function once more, this time to introduce additional parameter which holds the results of computations up to a given call:

int factorial( int n ) {
return factorial_help( n, 1 );
}
 
int factorial_helper( int n, int acc ) {
if ( n == 0 ) return acc;
return factorial_helper( n - 1, n * acc );
}

Let’s see how it works:

factorial( 3 ) ->
  factorial_helper( 3, 1 ) ->
  factorial_helper( 2, 3 * 1 ) ->
  factorial_helper( 1, 3 * 2 ) ->
  factorial_helper( 0, 6 ) ->
  6

That was simple, wasn’t it? This technique can be used practically always, but it’s not always effective (e.g. when building lists). Does this mean you can use this trick to in your C or Java programs? Well, you could write your recursion using accumulator, but neither Java nor C are required to perform tail call optimization (they might do it in some cases, but they don’t have to in general), so performance of your programs could decrease (more parameters to copy). This is especially a problem for Java, since there are functional languages that run on Java Virtual machine (Scala and Clojure) and that cannot use tail call optimization2. Let my quote a paper “The role of study of programming languages in the education of a programmer” by Daniel P. Friedman:

“We don’t want to be bothered with design flaws that have been dropped into languages by well-meaning designers and implementators. Some example of this are (…) Java’s lack of support for tail calls. There are likely very well-intentioned reasons for these mistakes, but mistakes they are, nonetheless. Guy Steele, (…) co-author of ‘Java Language Specification” now works for SUN and he has communicated with me that he was promised back in 1997 that this flaw would be fixed. Here it is 2001 and there is still no resolution of this problem on the horizon.”

It is 2012 and still no solution. I won’t get deeper into this matter (I don’t feel sufficiently competent for that), but if you’re a Java programmer than reading this might be interesting.

“What should I do now?”

So what languages are properly tail recursive? That’s a good question and I’m still trying to figure out the answer. Certainly Scheme (see: R5RS, section 3.5) and Erlang (but see the Erlang myths). Haskell is… ummm… different and I don’t yet fully understand it’s memory model (check here and here). As I said, some compilers of C and Java can sometimes optimize tail recursion.

The most important question is: should we really care to use recursion? As I said in the beginning, many computer science problems are recursive by nature, but whether you approach them in an iterative or recursive approach mostly depends on your language. In Java it would be unnatural to process a list using recursion. In Haskell or Erlang it’s idiomatic, since these languages have the operator to get the head of the list (tail of the list is the processed recursively) but they don’t have looping constructs. Most of us programmers expect a simple answer and when we have it we follow assume-don’t-verify policy. I think there is no general rule for tail recursion. There are cases when it’s faster, there are cases when it’s slower so you really have to measure the performance and choose the faster algorithm. You also should be aware of compilers internals, how it optimizes your code, how it calls functions, manages parameters and so on.

I’ve been learning FP for about 3 months now and I must say that approaching problems in a recursive manner have changed my point of view greatly. I find recursive solutions much easier to understand because they are constructed by decomposing the problem into simple cases. This is easier to code and therefore less error prone, so the more I program in Scheme or Haskell the more I wish Java had features of functional languages. If you’re still not convinced about power and usefulness of recursion then perhaps you should read this.

UPDATE (05/04/2012): Tail recursion and TCO is also discussed in fourth chapter of Real World Haskell (read it here).

  1. Try googling iterative version of Quick-sort algorithm to see a good example of this. []
  2. Clojure has a workaround for this []

Installing GHC on openSUSE Linux

The first thing you do when starting out with a new programming language is of course installing a compiler and an IDE. Although this first step should be easy, it took me a lot of work to get Haskell running on my openSUSE Linux. The solution to my problems turned out to be obvious, as all solutions are when you already know them. Nevertheless, 5 hours of my life went to waste and all I can hope for right know is saving others from repeating my mistakes.

There are two main Haskell compilers: GHC (Glasgow Haskell Compiler) and Hugs. I decided to use GHC, as it seems to be the more popular one. As a Linux user you have three options of installing GHC:

  1. Use the package repository
  2. Install precompiled binaries
  3. Compile from source

The third option is not really a sane option – GHC is written in Haskell so you would need working Haskell compiler to compile it. The first option seems to be the most natural for Linux user. Don’t we like to have our software managed from one central package management application? Good news: there is Haskell repository for openSUSE. However, after I installed GHC and some libraries from this repo it turned out the the compiler doesn’t recognize the libraries. Solution: for each library install both the normal and the devel package. Obvious, isn’t it? Well, it wasn’t obvious to me at first and I still think it’s a bit tricky. You install the compiler (which means that you most likely want to compile programs), YaST resolves the dependencies by installing additional GHC libraries, but compiler doesn’t have access to these libraries (since devel packages were not installed) and in the end GHC is totally useless. Where’s the logic?

There is one more catch with the repo. Haskell community offers a web repository of additional Haskell packages called Hackage. Not every package available via Hackage is also available in the openSUSE repository. Most notably Leksah, the Haskell IDE, is not available. So what now? Luckily with Haskell comes Cabal (Common Architecture for Building Applications and Libraries). Cabal is a package manager that manages packages available to GHC. It resolves package dependencies, downloads packages from the web, compiles and installs them. This however leads you to mixing two ways of managing GHC libraries. Some libraries will be managed by Cabal and some by YaST (or other rpm/deb management tool if you’re using different brand of Linux). This, at some point, may cause problems which leads us to the last of three installation option: using precompiled binaries. If you choose this option, carefully to chose which GHC version to download. The most obvious choice is using the latest available version, right? Wrong! You see, there is a thing called The Haskell Platform, which is a set of basic Haskell libraries required for development. New versions of Haskell Platform are released twice a year and each version is compatible with a particular version of GHC (most likely not the latest one). At this moment the latest version of GHC is 7.4.1, but the latest Haskell Platform supports GHC 7.0.4. If you’re a newbie, just like me, it is very reasonable to set up your basic Haskell environment by installing the Haskell Platform.

So, my advice on installing GHC on openSUSE (and other Linux distros) is: don’t use the repo, use the precompiled binaries. Instead, get the Haskell Platform, get the supported GHC version, install GHC, install Platform and then fell free to use Cabal to install any additional libraries from Hackage.

UPDATE (06/06/2012): The installation method described above can be enhanced. Read this follow-up for more information.

Diving into functional programming

I started programming when I was about twelve years old. Me and my friend got a book about writing programs in QBasic for Amiga. At first we were just copying code from the book. Later I started to make my own code. It was crappy – I wasn’t even able to use functions – but it got me hooked. Soon I moved to Pascal and got slightly more advanced. Not only did I learn about functions but even about objects :-) When I was in high school (age 16 or so) I began coding in C++. After high school the choice of studies was obvious for me – computer science. I went to Technical University of Łódź, biggest technical college in my city and one of the best in Poland. During studies I learned a lot about programming. Java became my main language for about 4 years, but I’ve had experience with other languages: Ada, Perl, Bash/AWK and Matlab, to name the most important. After graduating in 2008 I got a job at my own department as a researcher and lecturer. Matlab became my language of choice, since I was doing research in digital signal processing. These research were successful enough to earn me a PhD.

What’s the point in me telling you this? As you can see, there’s been a lot of programming in my life. If I were to name one thing I am really good at, these would be it. I was always convinced that I can code everything and I have all the fundamental knowledge of that field. I was wrong.

What programming paradigms are there? There’s the dominating object oriented programming paradigm and there’s structural programming, often treated as a contrast to OO programming. Everyone knows these two, at least I knew them. I also knew about the existence of Prolog and therefore the logical programming paradigm. But there is one more paradigm, which I wasn’t aware of: functional programming. I first heard the term ‘functional programming’ about four months ago and I started to be inquisitive. Is there really some different way of writing programs that I am not aware of? It turns out that yes, there is. During last months I realized how little I knew about programming and how many ingenious concepts were hidden away from me. I don’t like to be ignorant when it comes to programming so I started learning about functional programming (which I will abbreviate as FP). This blog will document my journey through this field. I’ll post various stuff on FP and other fields of computer science. I hope that sharing my knowledge will give others the motivation to explore this fascinating subject.

Staypressed theme by Themocracy