recursion in programming

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

Recursion is actually quite simple. It’s a subroutine calling itself. Its 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 whats called the quick-sort.

After reading the a Wikipedia article you are probably going yuck already. So lets 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 a 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 its 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 its 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 is 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 its 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

23 replies
Newer Comments »
  1. jedishrfu says:
    Yes, they had an area to save the registers prior to the call. Some registers were then loaded with argument pointers and upon return the registers were reloaded with their older values.
  2. bhobba says:
    The programming language I mostly used, called Natural, allowed recursion but few used it, and those that were called upon to maintain the few that did tried to avoid it like the plague; buck pass it whenever possible. Interestingly many programs that were put in the too hard basket were often solved using an array as a stack. One that did the rounds I originally wrote but ran too long. What it did was a heap of database searches to update things. It was possible to store a direct pointer to the database record rather than search for it, and if you do that it retrieved records much faster. So I figured maybe it was retrieving many of the same records a lot, and on a punt kept a copy of the records location in a large array I used as a stack. I searched that first before searching the database. Amazingly it cut run time to about an hour from all night.

    Thanks
    Bill

  3. jedishrfu says:
    I’m sure programmers before him used variations of the stack. He was likely the first to describe it clearly in the literature though.

    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.

  4. neilparker62 says:
    One can easily experiment with recursive routines on Excel.

    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.

  5. anorlunda says:
    Recursion is often the result of more complicated situations than a function calling itself. For example …

    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.

    There are a couple of situations where recursion is prohibited. The first is related to safety standards …

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

  6. DEvens says:

    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.

  7. PeterDonis says:
    CPython, the reference Python implementation, doesn’t do tail call elimination and Python’s inventor has said they have no intention of changing this, so there’s little point in writing tail-recursive code in Python.

    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.

  8. anorlunda says:
    Fun article @bhobba. Thanks for sharing.

    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.

  9. Mark44 says:
    If you want to understand recursion better I suggest learning the programming language LISP.

    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

    (defun to-hex(num hexDigitsList)    
        (defvar quot -1)
        (defvar remainder -1)
    
        (setq quot (floor (/ num 16)))
        (setq remainder (mod num 16))
        (push remainder hexDigitsList)    
        (if (> quot 0)
            (to-hex quot hexDigitsList)
            (progn    
                (format t "Hex:    0x")
                (loop for hexDigit in hexDigitsList
                    do (format t "~X" hexDigit)))
                ))

    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.

  10. PeterDonis says:
    I think it could be modified to do that though

    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

    def factorial(n, result=1):
        if n == 0:
            return result
        return factorial(n - 1, result * n)

  11. bhobba says:
    Said one mirror to her mother
    as they gazed at one another:
    I see an eternity unfolding
    Endlessly onward like no other.

    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 :cool::cool::cool::cool::cool::cool::cool: – 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

  12. jedishrfu says:
    Yes, a good example of this is when you make an expression parser. You can use recursion by using the parser itself to evaluate parenthesized expressions to any degree limited only by your memory. As an example:

    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

  13. fresh_42 says:
    I’m not sure where recursion comes in here, but I found the timely coincidence somehow fitting:

    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.

  14. jedishrfu says:
    Stack isn’t a problem with many functional languages because of tail call elimination.

    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

    de factorial(arg):
        if arg==0:
            return 1
        else:
            return arg * factorial(arg-1)

    I think it could be modified to do that though:


    Python

    de factorial(arg, result):
        if arg==0:
            return result
        else:
            factorial(arg-1, result*arg)

    to run:


    Python

    factorial(arg,1)

  15. jedishrfu says:

    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/

  16. Mark44 says:
    I would often face a StackOverflow exception, presumably because the recursion didn’t terminate as the base case was ill-defined.

    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.

Newer Comments »

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply