Recursion in Programming and When to Use or Not to Use It

Recursion is actually quite simple. It’s a subroutine calling itself. It’s surprising but some problems that look quite hard can be trivial using recursion – but be wary – as I hope to explain there are traps you need to consider especially if working in a team environment.

When I studied Computer Science the first language I learned was FORTRAN. You can’t easily do recursion in FORTRAN (my lecturer went so far as to say it can not be done, but a google search will show that’s not quite true – however for this article, I will assume you can’t). At the end of the FORTRAN part of the course, they devoted a couple of weeks to Pascal to explain its advantages and disadvantages compared to FORTRAN. Pascal does allow recursion so that’s where I first cut my teeth. The other major language in those far-off days was COBOL. Some versions allow it, but the general advice is, like FORTRAN – forget it. However FORTRAN and COBOL are not modern languages – most modern languages allow it. To really understand recursion you need to write an assembler program that uses it. When I did assembler I had to write what’s called the quick-sort.

After reading the Wikipedia article you are probably going yuck already. So let’s start with the usual first recursive program people write – The Towers of Hanoi.

Go ahead and write and run it. You will learn a lot. It was the first recursive program I write using PASCAL. Since then I have written many more and gained a lot of experience when and when not to use it. Wikipedia goes deeper into Tower Of Hanoi and will help in starting to understand the issues involved.

When you have a problem to solve, sometimes a recursive solution leaps out at you. But from long experience in that ultimate educational institution, the school of hard knocks, that is the point to stop and say – be careful. Here is an example – calculating factorial n ie n(n-1)(n-2)……1. A recursive solution is easy – simply have a subroutine Factorial(n). In structured English

Factorial (n)
If n = 1 return 1
else
return n*Factorial(n-1)

A little note to newish programmers. As you start your programming journey some textbooks get you to use flowcharts etc. IMHO structured English is preferable.

Eventually, you will progress to having a lot of programs and you pick the one closest to the one you want to write then hack it. What was it one of my teachers said – first-year students – coders – you wrote directly in the language you are using, second-year – programmers – you wrote structured English – third and fourth year – hackers. But while the recursive code for factorial n is easy it’s also easy to write just using a loop. Go ahead and write a loop version in your favorite language, then compare the two solutions. What do you notice – the recursive solution is slower. Why is that? Well, it’s got to do with what happens when you call a subroutine. It needs to return the program to the state it was before calling the subroutine. That means it needs to store a lot of information before executing the subroutine and when you return restore it back. That takes time a loop solution does not require.

In the version of Pascal, I used it gets put in an area called the stack. Other things the program needs to store are put in an area called the heap. As you mucked around with recursion more and more you eventually get the dreaded message – stack overruns heap. You can guess what the compiler was doing – they had a program area – at the top, you had the stack with information going downwards – at the bottom, the heap had information going upwards – and if they collided – bye-bye program. To really understand it you need to write a recursive program in assembler like I had to do with the quick-sort. As an aside, the lecturer was initially kind and gave us the Tower of Hanoi to write in assembler. Only something like 25% of students did the assignment, which made the lecturer mad, so we all had to do the quick-sort – some lecturers are wonderful people.

Well, I eventually graduated and went out into the big wide world. I went to the Australian Federal Police and learned one thing very quickly – programmers want simple code and generally hated recursion. I had to write a program to scan links in an intelligence database. Normally most IT departments at that time used COBOL – so no recursion. But we had recently switched to a language that allowed recursion (NATURAL for those that know NATURAL/ADABAS from Software AG). Now I had the choice. It would be easy to simply scan the records then recursively scan the links. Easy – but you have possible speed issues like the factorial program, and since most other programmers were used to COBOL possibly never even seen recursion before. So I decided on a loop-type solution. Later when I worked in another department there was a letter engine written by someone else that used recursion.

Nobody wanted to work on it – it always ended up on my desk. I gave it to one of my staff. He complained to my boss – it was too hard. Eventually, he went to work for another area and basically just wrote some simple reports. He was much happier. Why? Well, I remember a cartoon where a new staff member was being shown around by the IT department head. He came across this guy surrounded by heaps of printouts poring assiduously over code. The comment made by the manager was – put him in front of a terminal and he is a genius but, otherwise, he is so boring and antisocial he will never break into management. No wonder some programmers want simple easy to understand programs not using advanced concepts – technical competence by itself may not be the ticket to advancement depending on the culture of where you work.

It can backfire to – but stories about that are way off-topic. Bottom line – best to keep it simple stupid. Actually, that’s often good advice regardless of what you do. Recursion can be hated by other programmers who later may have to maintain it, so my recommended rule of thumb is – only use it if you think it’s worth doing. That’s why the ancient bible on programming – The Art Of Computer Programming by Knuth has that critical word in it – ART.

Comment Thread