recursion in programming

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

[Total: 2    Average: 5/5]

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

16 replies
Newer Comments »
  1. Mark44
    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.

  2. jedishrfu
    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/

  3. jedishrfu
    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)

  4. fresh_42
    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

    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.

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

  6. jedishrfu
    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

  7. bhobba
    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 Lamda Calculus. For some info about LISP (including writing a Lisp interpreter) and the Lamda Calculus, plus some info on an interesting language called HASKELL see:

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

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

    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:

    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

  8. PeterDonis
    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)

  9. Mark44
    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.

Newer Comments »

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply