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

My favourite interest is exactly how can we view the world so what science tells us is intuitive.

This is not always true. Some languages (for example, Lisp) implement loop constructs using recursion, and have optimizations for common cases of recursion that eliminate the increase in time and space complexity (for example, tail call optimization).

A better general argument would be that loops are much easier for programmers to reason about than recursion, so that, even if your language implements loop constructs using recursion, it still benefits from having the loop construct because it is easier for programmers. In most cases these days, it is much more important to optimize programmer time than to optimize computation time, since the former is far more expensive than the latter.

That’s a very good example because most programming languages that I have seen use recursion in

definingwhat constitutes a valid statement in the language.Is the above relevant to anything in this thread? We seem to be getting far afield from the Insights article on recursion.

Thanks

Bill

I remember implementing a data stack in programs I wrote in BASIC for a CS class on data structures. My computer could handle recursive calls in BASIC but not with data so I implemented an index that I incremented and decremented as I traversed the recursion. My data values were stored in arrays referenced by the index.

FORTRAN on mainframes in the 1970s didn’t have recursive capabilities. If you tried it you get caught in a loop.

The reason was return address was a single location so sub A could call sub B and sub B could call sub C but if subs B or C called A then the return address would point back to them and not the original caller.

Example 1: the Fibonacci sequence:

Cell A1 = 1

Cell A2 = 1

Cell A3 = A1 + A2

Then copy/paste the formula in Cell A3 to (n-3) cells below for n terms in the Fibonacci sequence.

Example 2: generate sine and cosine (actually we’ll use versin(x) which is 1 – cos(x)). Let x = pi/6

Cell A1 = pi()/6*2^(-10), Cell B1 = (pi()/6*2^(-10))^2/2

– these are small angle approximations for sine and versin the smaller the angle the better the approximation.

Cell A2 = 2*A1*(1-B1), Cell B2 = 2*(A1)^2,

– doubling algorithm.

Copy/paste the doubling formulae in cells A2 and B2 to the next 9 rows to determine sin(pi/6) and versin(pi/6). Obviously cos(pi/6) is easily obtained from 1 – versin(pi/6).

Example 3. Home loan balance given fixed interest rate and monthly payment.

Cell A1 = 1e6

Cell A2 = A1*(1 + 0.01) – 11010.86

Copy / paste the formula in A2 to next 239 rows where n=240 is total no of months (period of loan). Graph your output to see the characteristic curve for loan balance.

That’s an excellent point, although I always called that re-entrant rather than recursive. You can get the same thing with real time programs and with parallel processing.

It would be clearer if the title emphasized recursive algorithms rather than recursive subroutine calls.

That is also an excellent point. There are some analogous prohibitions on use of virtual memory in time-critical safety-related programming.

OK, much as the idea of applying the quicksort algorithm to the Tower of Hanoi problem is intriguing… I still don’t know when and when not to apply recursion. I know two situations where it’s at least worrisome and should be carefully considered before applying.

If each level of the problem has complicated, large, or difficult-to-initialize data, you may not want to use recursion. Unless there is some easy way to use the same copy of this stuff and somehow increment a counter or pointer or some such. You don’t want to make a brand new copy of your entire database at every level. It’s going to use way too much memory and way too much time.

If the scheme can branch, especially if it can produce a huge tree, you may not want to use recursion. Maybe, for example, recursion is not the way to play chess. Even a few moves can produce an enormous tree. Or at least, not naive recursion. “Pruning” is one of those descriptive buzzwords that gets you on a potentially useful track. But even a pruned chess tree can be daunting.

Another aspect of recursion is, you may want to have a helper function. Call the helper function to do the prep work such as checking ranges, pestering the calling function with error messages, etc. Then the recursion function can be simpler. In the factorial example, you would not need to check that the input value was greater than 0 in recursive routine, only in the helper routine. It checks that the argument is in a valid range then calls the recursive routine. Other possible uses for the helper function are quite simple to imagine.

There are likely other situations I have not considered that will produce troublesome behavior with recursion.

I think there have been some attempts to implement tail call elimination in CPython by bytecode manipulation. I don’t know that I would recommend that in a production system, since bytecode manipulation is usually considered non-standard, but it’s possible.

Count me among the programmers who favored KISS over recursion. I never did find a case where I thought it was actually needed. That is until the day I first read about MapReduce.

https://en.wikipedia.org/wiki/MapReduce

When you introduce the complexity of parallel processing, and distributed clusters of computers, then a simple loop won’t work, and the elegance of MapReduce greatly simplifies things.

https://en.wikipedia.org/wiki/Clojure

Which is something I am attempting to do at the moment. My first experience with Lisp was in about 1982, with an implementation for the Apple II computer. I couldn’t see the point of it at the time. Since then, I’ve realized that there are a lot of good reasons to become acquainted with this language.

Since this is a thread about recursion, I should mention that virtually every discussion of recursion in any programming language that supports this feature includes the factorial function as an example. It’s almost as if there were no other possible uses. Because I teach classes in C++ and MIPS assembly, I try to come up with examples other than those that typically are in textbooks.

Here’s an example in Lisp that I wrote that converts a nonnegative decimal integer to its hex form.

Code

The underlying algorithm is this:

Given a nonnegative decimal number,

Divide it by 16 and save the (integer) quotient and remainder.

If the quotient is positive, call the routine again with the quotient as the first argument,

Otherwise, display the list of remainders.

For example, if the function above is called with decimal 100 as the argument, the first call produces a quotient of 6 and a remainder of 4.

In the second call, the new quotient is 0 (6 / 16 == 0 in integer division), and the remainder is 6.

Since the new quotient is zero, we display the remainders

in reverse order, resulting in the hex value of 0x64.A routine to convert decimal numbers to their binary form is nearly identical, with the main difference being that you divide by 2 each time rather than by 16.

Any process that needs to produce results in the opposite order they were generated is really a natural for recursion. Other examples include displaying a string in reverse order and checking for palindromes.

With a simple refinement using Python’s ability to define a default argument you can eliminate the need to include the "result" variable in the initial call:

Python

If you want to understand recursion better I suggest learning the programming language LISP. It was the second language developed just after FORTRAN, but is influenced by different principles, namely the Lambda Calculus. For some info about LISP (including writing a Lisp interpreter) and the Lambda Calculus, plus some info on an interesting language called HASKELL see:

https://crypto.stanford.edu/~blynn/lambda/

For the seminal paper on LISP see (note only for advanced computer science students):

https://aiplaybook.a16z.com/reference-material/mccarthy-1960.pdf

For the average Hacker – yes I progressed from programmer to Hacker – the following is better:

http://languagelog.ldc.upenn.edu/myl/ldc/llog/jmc.pdf

I read somewhere of an interesting experiment where they asked programmers to solve problems in various programming languages to see which language got a working program fastest. Surprise surprise, the winner was the second oldest language – Lisp. Amazing. BTW I do not use LISP – I use PYTHON then tweak it for performance with LUAJIT if I have to:

http://alexeyvishnevsky.com/2015/05/lua-wraped-python/

Another good exercise is what my teacher made us do – write the Quick-Sort in assembler. Actually these days you would use C that allows the embedding of assembler. You learn a lot but I do not have fond memories of doing it – I avoid assembler whenever possible – I find LUAJIT plenty fast enough and much easier to understand and maintain.

Actually these days I do very little programming. 30 years of it was enough for me. I remember when I started loved programming however slowly but surely it lost its ‘charm’. Another reason to try and break into ‘management’, but that has its own issues that would be way off topic for this thread.

Thanks

Bull

The expression ((2+3)*4 + 5*(6 -7))/(5+7)

ParseExpr sees ((2+3)*4+5*(6-7)) and (5+7)

Called again for the left expression (2+3)*4 + 5*(6-7)

Called again for 2+3 returns a 5

Then evaluates 5*4 to get 20

Called again on 6-7 returns a -1

Then evaluates 5 times -1 to get -5

Then evaluates 20. – 5 to return 15

Called again for 5+7 returns 12

…

https://www.physicsforums.com/threa…ths-12-23-1-5-win-a-book.935250/#post-5912694

as they gazed at one another:

I see an eternity unfolding

Endlessly onward like no other.

Recursive language and modern imagination were acquired simultaneously 70,000 years ago

https://archaeologynewsnetwork.blog…-language-and-modern.html#I63oCfC8CmXtWEhC.97https://riojournal.com/article/38546/

Maybe I should have posted it in our lounge as your insight provoked some good jokes about recursion. Seems there is more to it than one might think.

This only works for a certain type of recursive function that once found bubbles the answer to the top. In contrast, the factorial is not a tail recursion amenable function because it modifying the results as it bubbles back.

Python

I think it could be modified to do that though:

Python

to run:

Python

Good article, Bill.

I liked the mention of FORTRAN. It’s true though, recursion was not possible until Fortran-90 when they added the notion of a stack (to keep up with C, I suspect). The early Fortran I used called Fortran-Y by Honeywell circa 1976, had a pass-by-reference scheme where addresses to data were stored is a specific data block by the subroutine/function when called or in CPU addressing registers for speed. Consequently, if it called itself then it would overwrite that same block and upon return would return to itself in an endless loop.

Also early Fortrans, because of the call-by-reference scheme allowed you to pass results back through your arguments which wasn’t a problem until you used a literal. So calling a subroutine with the literal 3 and with the subroutine changing the value to 6 meant that all through your program wherever a 3 was used now became a 6. That was a very tricky problem for the unwary programmer to debug.

Later Fortrans, most notably Fortran-90, adopted the notion of the stack allocating the data block on the stack and a call-by-value scheme allowing you to implement recursive functions while protecting against changes to your arguments getting passed back up the line.

As Mark said, recursion was cool but it tended to use a lot of stack space for deeply recursive calls imagine factorial(10000) which would call the factorial function about 10,000 times and returning intermediate results about 10,000 times back to the original call. In C code, the stack would grow into the heap space so if you allocated too much memory or you recursed too much they would collide and end in an explosive collision (actually your program would just crash).

In our class, we implemented Ackerman’s function which was said to be a good memory tester and showed the dangers of recursion.

https://en.wikipedia.org/wiki/Ackermann_function

LISP and PROLOG used recursion built into their language. They even had to implement a speedup called tail-recursion for functions that had this behavior to get back faster instead of popping the stack and returning through each level. The factorial function can’t be optimized in this way. You can see an example in the link below where a max value once discovered is returned up the stack.

https://www.csie.ntu.edu.tw/~course/10420/Resources/lp/node38.html

Thanks for writing and sharing this article.

Jedi

PS: while researching my comments I found this reminiscence of the halcyon days of Fortran:

https://hackaday.com/2015/10/26/this-is-not-your-fathers-fortran/

This is a good lesson about using recursion — namely, that you need a clear-cut way for recursion to terminate. Not mentioned in the article was how recursion relies on the stack for parameter passing.

One problem with recursive functions is that even if you have a proper terminating case, it’s still possible to overflow the stack if the routine calls itself too many times. This is less of a problem with modern computers due to the much larger RAM available for stack storage.