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

[bhobba]

Recursion is 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...

Continue reading...

 

[Wrichik Basu]

That was a good article. It is true that many of us, especially the beginners, tend to use recursion without even understanding it's complexity for larger inputs. While teaching Python, our Professor was stressing the same. Often, when we need to find the sum of a series correct upto certain decimal places, we tend to do it in a straightforward fashion. But our Professor stressed that we should rather try to find how the nth term depends on the (n-1)th term, and then use that in the sum. In this way, factorials can often be ignored completely.

I do remember that when I used to do programs on data structures in Java using SLL, DLL or circular LL, I would often face a StackOverflow exception, presumably because the recursion didn't terminate as the base case was ill-defined.

 

[Mark44]

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.

 

[DavidSnider]

Stack isn't a problem with many functional languages because of tail call elimination.

 

[jedishrfu]

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.

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

I think it could be modified to do that though:

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

to run:

factorial(arg,1)

 

[fresh_42]

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.

 

[jedishrfu]

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

 

[fresh_42]

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

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

 

[SSequence]

Originally I didn't understand how to use recursion (even for simple problems). The reason was [which is probably true for many other people too] that while I understood on a (mechanical) level what did it do [or at least had a good idea], I didn't get how it was justified to use it to solve common textbook like problems.

Later on, four or five years later (after being out of undergraduate), when I picked it I managed to understand how to apply it to solve very simple (textbook like) problems. To me the assumption that calling to smaller sub-routine would solve the smaller problem now made sense. One of the reasons was that I felt that (if needed) I could get down to it and justify a (near) formal proof [in an idealised setting ... possibly after removing some extra burden/rules of a given language] using induction.

Now two or three years later again (just around the time of joining this forum), I decided to formulate a (finite) computational model for myself [not for execution on anything real etc.]. There were three or four reasons I felt it was a good idea, which I won't go in detail here. I am not educated about the formal studies of PL, so I [somewhat informally] wrote the rules to a certain reasonable level of detail (just for myself mostly).

Now one thing I realized was that [at least in the (very) simple procedural style language that I set-up] a language using recursion can simply be viewed as one where: when you write-down in detail the "dependence chart" for the way the functons call/use other functions, there is a cyclical path. In other words, the "call dependence hierarchy"(or whatever we want to call it) can contain a cyclical path.

Anyway just a basic observation that I thought I might share. I don't have a particularly good idea how this definition would generalise when we talk about more and more complex and extra rules in a PL.

 

[jedishrfu]

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

 

[bhobba]

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

 

[PeterDonis]

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:

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

 

[SSequence]

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.

Just to clarify a bit, there are two different senses one can interpret "call-dependence hierarchy". One is the aspect of evaluation. The other is dependence which can just be tracked by looking at the program.

============

Evaluation aspect is how a function say with a signature like:
int f(int x)
is evaluated when we make a specific call like f(100) etc. That is, how many further function calls are required (and with what structure+rules) to evaluate the given value f(100).

As I understand, if the language is very very simple, then giving a precise delineation of such rules (for recursion) isn't that difficult (though it would definitely take some work when stated precisely).

============

However, I was using the term in the following sense (just giving one specific example):
Suppose that the function "f" (in its body) calls "g"
The function "g" (in its body) calls "h"
The function "h" (in its body) calls "f"

So there is a cyclical path in the sense of:
f→g→h→f

============

Anyway, I am not particularly knowledgeable about the topic (apart from just knowing the basics) so I will give it a rest here.

 

[Mark44]

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.

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

 

[DavidSnider]

If you want to get into LISP the "Structure and Interpretation of Computer Programs" book and lectures are amazing and free. I so wish I had seen these when I first started coding.

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/

 

[jedishrfu]

There's also a modern variant to Lisp: Clojure that runs on the JVM and thus can run on a variety of the same platforms as Java. It can also interoperate and use Java jar libraries.

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

 

[anorlunda]

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.

 

[rcgldr]

The article doesn't do a good job of explaining when to use and when not to use recursion, even though that is the title of the article. A few example for each case would help.

With recursion, making a problem smaller doesn't make it simpler until it reaches some simpler base case. When developing recursive algorithms, it's common to start with a base case and work backwards to larger cases in order to write a program. The Tower of Hanoi algorithm would be difficult to figure out how to program without starting with the base cases first.

If the data for a process tends to be a nested structure, then the code to work with that data would also tend to be nested (recursive). Examples of "nested data" are tree structures, nested directories on a system, ... .

In cases where data is not nested, such as an array or linked list, algorithms such as sorting algorithms may be recursive or iterative, depending on the algorithm. In the case of quick sort, each level of recursion brings the data closer to a sorted state. In the case of merge sort using an extra working array and indexing, a top down recursive approach accomplishes nothing during recursion except to generate and push index pairs onto the stack until an index pair corresponding to a single element is produced, and only then does any actual merging take place. A bottom up iterative merge sort skips the recursion, treating an array of n elements as n runs of size 1, and starts merging immediately. Most libraries for merge sort are some variation of bottom up merge sort (like tim sort), but most learning exercises involve top down merge sort, and I'm not sure why this happened. For linked lists, iterative bottom up merge sort is faster than recursive merge sort (which has to scan lists to split them).

Fibonacci is another case where recursion is relatively expensive, as the recursive version involves about Fib(n)-1 instances of the function (exponential growth), while an iterative version can be implemented using 2 or 3 variables to hold the sums.

APL was the first recursive programming language I used, but the main difference in APL is that it's native operators (most of them greek symbols) work on scalars, vectors, matrices, or "tensors" (matrices with more than 2 dimensions).

Cobol and Fortran may not be "modern languages" but they are still in use today.

 

[wle]

This only works for a certain type of recursive function that once found bubbles the answer to the top.

It also only works in certain programming languages or certain compilers/interpreters that eliminate tail calls. 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.

There's also a modern variant to Lisp: Clojure

Clojure is frequently marketed this way. It's misleading since it suggests Lisp is somehow "unmodern" and obsolete compared with Clojure. The truth is that Clojure is a largely different language from Lisp that does some significant things differently (e.g., lazy vs. eager evaluation, functional vs. multiparadigm language) which have advantages as well as disadvantages compared with how Lisp does things.

Running on the JVM is also not unique to Clojure; there are implementations of both Common Lisp and Scheme that do that. There's a difference though: Lisp and Scheme merely can run on the JVM, and can let you access Java libraries if you want, but are otherwise self contained languages. You could write Lisp or Scheme and not care if your code happens to be running on the JVM or somewhere else. Clojure by contrast actively exposes the Java ecosystem. If you use Clojure you very soon find you need to access Java classes and methods to do basic things, and if there are errors in your code you'll be confronted with Java exceptions and Java stack traces.

 

[wle]

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.

The thing with recursive functions is that they save a copy of all the function arguments and local variables on the stack for each recursive call. (Unless your code is tail recursive and your language or compiler recognises and eliminates tail calls, as mentioned earlier.)

The factorial is a good example to illustrate what recursion is but it is usually a bad example to illustrate where recursion is useful, since it has no real advantage over the iterative version and it has a serious disadvantage: it uses more memory and it needlessly risks overflowing the stack.

A better example of where recursion is useful is walking a tree. This is because while doing this you need to save, at all times, the path you followed down the tree to get to where you currently are so that you can backtrack. In an iterative version you would need to manually update a stack with this information. The recursive way is much easier and cleaner since this information is already saved on the call stack for you automatically and you can just use that.

A simple tree walker, which applies a given function to every item in a tree, can be done like this in Lisp:

(defun maptree (function tree)
  "Apply FUNCTION to every item in TREE."
  (typecase tree
    (cons (maptree function (car tree))
          (maptree function (cdr tree)))
    (t (funcall function tree))))

For example, running

(maptree #'princ '(a (b . c) ((d . e) . f) . g))

prints "ABCDEFG" to standard output.

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

(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)))
            ))

There are some problems with this which you'll probably want to know about if you're learning Lisp. The serious one is the use of defvar inside the function body:

    (defvar quot -1)
    (defvar remainder -1)

defvar defines a global variable* so you would rarely if ever want to use it inside a function. If you want to declare local variables then the basic way to do that is using 'let', although in your case it would probably be better to use 'multiple-value-bind' since Lisp's floor function computes both the floor (result of integer division) and mod at once and returns them as two separate return values:

  (multiple-value-bind (quot remainder) (floor num 16)
    ...)

Other than this, some style issues are:

• Your code is only recursive in the technical sense that your function calls itself. The algorithm you are using is really an iterative one and you don't gain anything from writing it in a recursive way.
• Part of what your function does is to construct a list of digits (in base 16) of the number. This is interesting and potentially useful enough that it should really be a separate function.
• Since the procedure is the same in bases other than 16, the base should really be a variable (possibly an optional one with a default value).

Putting it all together I'd probably do something more like this:

(defun digits (number &optional (base 10))
  "Return a list of digits in NUMBER."
  (loop with digits = ()
        with mod
        while (plusp number)
        do (setf (values number mod) (floor number base))
           (push mod digits)
        finally (return digits)))

(defparameter *base-alphabet* "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ")

(defun digit->symbol (digit)
  (aref *base-alphabet* digit))

(defun print-number (number &optional (base 10) (stream *standard-output*))
  (if (zerop number)
      (princ (digit->char 0))
      (dolist (n (digits number base))
        (princ (digit->symbol n) stream))))

In "real" code you might also want to add some type checking, e.g. make sure 'number' is an integer and the base is between 2 and 36.

Lastly, in case it isn't obvious to someone, this only makes sense as an exercise since Lisp's built-in format function already supports printing integers in hexadecimal (actually, any base between 2 and 36) as well as Roman numerals and written English:

> (let ((x 42))
    (format t "~d = 0x~x = ~@r = ~r.~%" x x x x))
42 = 0x2A = XLII = forty-two.

*defvar also does something else: it globally declares that the variable will be dynamically rather than lexically bound. The first answer to this Stack Overflow question explains what this means. The important thing is that this globally affects how code accessing the variable (or any variable with the same name) works, to the point that Lisp programmers use a special naming convention for global variables to avoid this happening by accident.

Any process that needs to produce results in the opposite order they were generated is really a natural for recursion.

This doesn't apply in this case. By iterating you go through the digits in reverse order. But then push adds the digits to the head of the list where you're storing them. This is why they end up in the correct order.

 

[PeterDonis]

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.

 

[rcgldr]

A better example of where recursion is useful is walking a tree. This is because while doing this you need to save, at all times, the path you followed down the tree to get to where you currently are so that you can backtrack. In an iterative version you would need to manually update a stack with this information.

In the case of a binary tree, an iterative version can modify the links between nodes for an in order traversal of a tree, such as a Morris traversal, which doesn't require recursion or stack. I don't know how well known this is.

 

[.Scott]

A couple of additional points:

There are a couple of situations where recursion is prohibited. The first is related to safety standards as in the transportation industry. For example, MISRA (automotive) prohibits recursion because of the difficulties in verifying that the code is operating as designed.
The other situation relates to how the stack is handled on many microprocessors. In those cases the build tools actually position local variables on a "stack" at link time - so the stack is not really dynamic.
So long as there is a known limit on the level of recursion, it is possible to write an algorithm without using recursion. Each level of recursion gives you another copy of your local variables. In the worse case, an array of structures can be used to hold those local variable sets.

Recursion is often the result of more complicated situations than a function calling itself. For example, an executable may open a dialog box that provides GUI options - some of which invoke dialog boxes. In such cases, the second invocation of the dialog box function is not just many function levels down from its parent dialog, it's actually invoked from a message loop that may be several levels down from the message loop supporting the parent box.

 

[anorlunda]

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.

 

[DavidSnider]

For example, MISRA (automotive) prohibits recursion because of the difficulties in verifying that the code is operating as designed.

That's interesting. Do they also limit what languages\compilers you're allowed to use?

 

[.Scott]

That's interesting. Do they also limit what languages\compilers you're allowed to use?

MISRA is specific to embedded automotive systems. I believe it specifies C or C++ standards exclusively - or rather, subsets of several releases of those language standards. As a matter of practicality, it requires automated support for MISRA compliance checking. So if those tools are not available for a development environment, that environment would not be practical to use.
Beyond the compiler, there is a requirement for controlling the impact of any single point of failure. So not just any microprocessor or any operating system can be used.

Wiki for MISRA C

 

[DavidSnider]

MISRA is specific to embedded automotive systems. I believe it specifies C or C++ standards exclusively - or rather, subsets of several releases of those language standards. As a matter of practicality, it requires automated support for MISRA compliance checking. So if those tools are not available for a development environment, that environment would not be practical to use.
Beyond the compiler, there is a requirement for controlling the impact of any single point of failure. So not just any microprocessor or any operating system can be used.

Wiki for MISRA C

Wow. This has led me down a rabbit hole of legal cases involving auto code not being MISRA compliant. Fascinating.

 

[Klystron]

As described in other posts above I also programmed factorial and Fibonacci functions in Pascal, first applying iteration then recursion at a time when stack / memory was quite limited. Lessons learned from Pascal progressed to practical recursion in Common Lisp. Applied sparingly, recursion made sense implementing tree traversals in game theory IIRC*, some counting algorithms and certain string manipulations such as recognizing palindromes and improving a codec.

Surprisingly, I once implemented recursive code in C/C++ to push pull bits within specialized flags on Sun Solaris servers. With space at a premium, I was able to code error signals from application function calls into a few 16 or 32-bit words. Recursion turned out to be the most efficient and fastest method to determine which functions had returned certain error conditions indicating incomplete intermediate computations without causing frame delays for other applications.

I wish I had code samples as it may have been machine specific but it worked well enough that NASA certified that flight simulator for full-motion hydraulics, a major milestone. The original systems code would freeze or otherwise invalidate the entire frame instead of marking an error condition to be corrected during later frames. IIRC* the 32-bit words were sectioned into 8-bit conditional variables that operated across multiple threads to ensure that downstream apps always used reliable data.

Before programming, I had studied recursion in relation to self-referential functions in linguistics and set theory. Offered without proof, self reference is a requirement for a recursive function but not all self-referential functions can be written recursively. These ideas were useful implementing reflective memory and also for self-adaptive run-time code such as the flags mentioned above.

*"If I remember correctly". I may lack the brain power now to remember the code I designed. These Insight articles are an excellent mental stimulus. Thanks.

 

[neilparker62]

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.

 

[rcgldr]

Historical trivia - Tony Hoare's original implementation of quicksort was done on a machine without a stack:

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

The program was iterative, using a program created stack that he called a "nest". Although he implemented actual code on that machine, it seems that the code was not archived, and instead there's a paper describing the general concept and the "nest" (which later was named "stack").

This "nest" aka "stack" was used to allow recursion on the 803, and used with a version of Algol that pre-dated Algol-60.

 

[jedishrfu]

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.

 

[Klystron]

[snip...]
"nest" (which later was named "stack").

This "nest" aka "stack" was used to allow recursion [...]

Apropos the terminology one of my old data structure textbooks used both terms but concluded that 'stack' was less ambiguous than 'nest' but retained the latter to describe 'nested FOR loops', 'nested functions', etc. Also, 'stack' was a popular term in electronics at that time. Interesting post.

 

[bhobba]

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

 

[rcgldr]

FORTRAN on mainframes in the 1970s didn't have recursive capabilities.

IBM 360 family to this day doesn't have a native stack. Instead there is a caller allocated save area, similar to X64 calling convention, except that the IBM save area is at least large enough to save all registers. At callee entry, R13 points to the save area, R14 is return address, R15 is base == entry address of the function being called . A linkage stack of save areas can be implemented by allocating save areas from the heap, then using those allocated save areas to allow recursion. Assuming the programming convention saves all registers, including R13, and R14 into the caller provided save area, then the current R13 points to the caller's save area, and that save area's stored copy of R13, points to the prior save area, providing a link chain (linkage stack) of save areas. When control is returned to the caller, the caller frees the allocated save area if not making another call. If a function does not make any calls, there's no need for that function to allocate a new save area, it will just use the save area provided by the caller.

 

[jedishrfu]

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.

 

[.Scott]

If you're looking for a worse case scenario for "no stack support", I submit the HP2100 series (circa 1967).
A call to a routine at location 300 would result in the return address being stored at 300 and execution beginning at 302. And I do remember writing code to support reentrancy on that machine.

I've been programming professionally for about 50 years. I believe I've used recursion a handful of times - but only two of any significance:

1) The ZigZag sort:
I actually got this sort from a ACM newsletter cover article (I recall the name was AACM at the time). It was originally intended to be implemented on a hypothetical parallel processing machine - but I adapted it for single processor use. I haven't used it in a couple of decades because now excellent sorts are part of regular libraries. But at the time, a sort that was sparing on memory, had good characteristics when run in a memory paging environment, and was efficient with processor resources made for a handy tool in any toolbox.

As I said, it is an "in place" sort - meaning that if you have "N" entries, you only need N+C memory locations to store the data where "C" is a small constant. In particular, that C is only needed when two elements are exchanged. So C=1.

The sort works most readily when N is a power of two, and it was originally implemented only for that case (and as originally implemented, it ran on "N" hypothetical processors in a 2^N configuration).

But here it is as pseudo-code:

   Sort(int direction, array a) {
      n=a.length()
      if(n>3) {
         n2 = truncate(n/2)
         Sort(direction,a[1..n2])
         Sort(-direction,a[n2+1..n])
      }
      Merge(direction,a)
   }

   Merge(int direction,array a) {
      n=a.length()
      if(n>3) {
         n2 = truncate(n/2)
         n3 = truncate((n+1)/2)
         for(n=1 to n2) {
           CompareAndSwap(direction,a[n],a[n+n3])
         }
         if(n3>n2) {
            // When number of elements is odd...
            if(Compare(direction,a[n3],a[1]) && Compare(direction,a[n3],a[n2]) n2 = n2+1
         }
         Merge(direction,a[1..n2])
         Merge(direction,a[n2+1..n])
      } else if(n>1) {
         CompareAndSwap(direction,a[1],a[2])
         if(n==3) {
            CompareAndSwap(direction,a[2],a[3])
            CompareAndSwap(direction,a[1],a[2])
         }
      }
   }

   Compare(int direction, element A, element B) {
      return ((direction>0) and (A>B)) or ((direction<0) and (B>A))
   }

   CompareAndSwap(int direction, element reference A, element reference B) {
      if(Compare(direction,A,B)) {
         element temp
         temp = A
         A = B
         B = temp
      }
   }

2) I ran into the other recursive application in the late 70's. The Defence Mapping Agency Aerospace Center produced charts for military pilots and wanted to put those publication on a computer - the Data General MV/8000.

In many cases, those "charts" were books. The books were printed as "signatures" (large paper sheets) with as many signatures per book as required. Each signature was 16 or 32 pages. Each page was 1 to 3 columns. Often, within each column there would be lists with several columns within the main column. So, as you went from book to signature to column to list column, you had 3 or 4 levels of recursion - depending on exactly how you counted them.

This recursion came into critical use just before publication when they wanted to "balance" the pages. The goal was to avoid leaving blank pages - better to have a little extra space at the bottom of each page that whole blank sheets at the end of the book. Similarly, if there were three columns on a page, it is better to put that content toward the top of the page than to leave a columns blank or unbalanced. And when a multi-column list was inserted, it should be balanced so as not to require more column space than the minimum. So the software would first run through all of the content to generate a table of small paragraph descriptions - how long the paragraph was, what level it was at (page, column, list), and how and whether it could be broken across columns/pages.
Then the processor would run through that table placing the content without attempting to balance it. This would generate the minimum number of signatures that would be required. A binary search would then ensue by adjusting the bottom margin, repopulating the pages, and determining whether the signature count had increased. If it had, then the margin was reduced. If not, it was increased. Ultimately leading to the perfect margin. This was repeated at the page and column levels to produce a completely balanced document. That binary search needed to occur within the recursion - and specifically whenever the content specified a page-break, a change in the page columns, or the end of a list. If that sounds complicated, there was one more wrinkle. The MV/8000 could not hold all of the table data at once - it had to be maintained in a disk file. To do this efficiently, the recursive algorithm needed to be adjusted so that it could make good use of the processor resources when working with an oversize table. The final results were paragraph-placing parameters that were saved in the table and later used to plot the originals for each signature.

 

[.Scott]

Why did I call this a "ZigZag" sort? ... in case anyone is interested.

After reading that original AACM article, I studied the algorithm and realized that it made for a good in-place sort for the reasons I described above. But before I adopted it, I wanted to prove to myself that it would really work under all conditions.

Of pivotal importance in this algorithm is the "Merge" operation. I'm using the term "Merge" loosely. What is actually done (as shown in the pseudo-code above) is that corresponding elements from two lists are compared and if needed swapped - so that the "smaller" (by collating sequence) is left in the first list and the larger is left in the second list.
But the sort will only work if the result of this "Merge" is that each of the elements of the first list is smaller than any in the second.

So I drew a chart for myself that showed the elements to be sorted along the X axis and their relative positions in the collating sequence in the Y axis. Before applying this Merge, the elements need to form a particular pattern in this chart. There will be a maximum and minimum element - and the elements need to be sequenced so that the collating sequence of all the elements between the min and max rise monotonically in both the +X and -X directions - with the chart wrapping around from the first element in the list to the last. If you think of the minimum element as the "Zig" is the chart and the Maximum as the "Zag", it has to be a simple ZigZag, with no extra Zigs or Zags (local minimums or maximums).

If you start with this ZigZag shape, fold it in half, and then perform the "merge", you get all the elements of low collating sequence in the first half, all those of higher collating sequence in the second half, and both of these sequences will have this same "ZigZag" property - allowing you to Merge them as well.

 

[jedishrfu]

Zig-zag bah! I shall name it the Mark of Zorro!

 

[.Scott]

Out of the night, when the full moon is bright,
Comes some code that is known as Zorro.

This bold engineer codes a 'Z' with his gear,
a 'Z' that stands for Zorro!

... I'll stick with ZigZag ... and the next time I will makes the collating plots look less like sword play.

 

[.Scott]

Here are a couple of more examples of recursion - the DFT and iDFT.
C Code for FFT.

I have coded the Discrete FT before. But never used explicit recursion to do it.

 

[Stephen Tashi]

Yes, a good example of this is when you make an expression parser.

That's a very good example because most programming languages that I have seen use recursion in defining what constitutes a valid statement in the language.

 

[rcgldr]

If you're looking for a worse case scenario for "no stack support", I submit the HP2100 series (circa 1967).
A call to a routine at location 300 would result in the return address being stored at 300 and execution beginning at 302. And I do remember writing code to support reentrancy on that machine.

Predating that, the CDC 3000 series (circa 1963), did the same thing, the first word was used to store the return address. There were other computers that also used this calling convention.

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

The calling convention for IBM mainframes going back to the IBM 360 doesn't involve a stack, instead the caller provides a save area, and for a call, R13 will point to save area, R14 will have the return address, R15 the base address of the function called. For recursion, each instance of a caller allocates a save area from the heap, and since R13 is saved in the save area, you end up with a linked list stack of save areas.

 

[.Scott]

@rcgldr:
You're right. I had forgotten about that CDC "RTJ" (Return Jump) instruction. I worked on a CDC 3300 at Lowell Tech - mostly in COMPASS (the macro assembler) and FORTRAN.

The RTJ instruction is documented on page 5-47 of the CDC 3300 Hardware Manual.

 

[vinaykhatri]

Recursion can be a very tricky concept for a beginner because its definition is very simple but the real-world uses are complex. Recursion is generally used when we want to call a function again and again until its hit a base condition.
The factorial of a number is very simple to use in the case of using recursion where we want to perform the same function n*factorial(n-1). until the value of factorial(n) becomes 1.
But using recursion is not that simple, by calling a function again and again n times takes a lot of resources and in this case, loops can be very handy tools to use.
So why and when to use recursion?
Although recursion can act like a loop, it can not be used as an alternative for a loop, the main reason is recursion can make a simple loop program complex and increase time and space complexity.
Recursion really shows when they are used in complex algorithms and data structures like searching, sorting, trees, and graph traverse. In these complex algorithms recursion really shines because these algorithms generally work on divide and conqure rules. Where we keep dividing the structure or data into half or sub-parts, and this is the power of recursion, where as loops can not be that useful in such scenarios.

 

[PeterDonis]

Although recursion can act like a loop, it can not be used as an alternative for a loop, the main reason is recursion can make a simple loop program complex and increase time and space complexity.

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.

 

[Mark44]

I've taught a lot of introductory programming classes over the years, mostly in C or C++, but also in other languages, such as Modula-2 (one time) and MIPS assembly (a half-dozen times). In all of these classes I've had students write programs that feature functions and in most I have assigned problems in which they write recursive functions.

A few years back I got interested in Lisp and wrote several programs in that language. More recently I have developed an interest in functional programming, and have been learning Erlang, a language that was developed by Ericsson AB, a Swedish telecom company.

In my classes, whenever I presented material on recursive functions, I tried to come up with examples other than the ubiquitous factorial function or the Fibonacci function, examples of which seem to appear in every programming textbook that covers recursion.

Two examples that I think are interesting feature recursive functions that 1) convert a decimal integer into its hexadecimal form, and 2) calculate the binomial coefficient $\binom {n}{k}$, also written as $~_nC_k$. The binomial coefficient gives the number of combinations of n items taken k at a time.

Here's the first of these, in Erlang. It converts a decimal integer to its hexadecimal form.

For some reason, the forum software wouldn't let me insert the code as text inside code tags, so I've attached the code as images. I've done a fair amount of testing, and this code seems to work well. Most of the work of recursion is done in the second toHexAsst() function, in which the last line calls the function recursively, making it tail-call recursive. In Erlang, a recursive function with tail-call recursion gets converted by the compiler into a loop, so there's not the problem of blowing up the stack if recursion goes too deep.

The other example calculates the binomial coefficient, $~_nC_k$. This is something I've never come across in my reading. I've omitted the comments I have in the code, but I'll provide a brief explanation here.

If f(n, k) = $~_nC_k$, a recurrence relation is f(n, k) = n*(n - 1) * f(n - 2, k - 1) / [ (n - k) * k].
So, $~_nC_k$ = n * (n - 1) / [(n - k)*k] * $~_{n - 2}C_{k - 1}$. The division here is integer division, which is guaranteed to be exact by virtue of the numbers involved.

By symmetry $~_nC_k$ = $~_nC_{n -k}$. For example, $~_8C_5 =~_8C_{8 - 5} = ~_8C_3$. This is easy to confirm by writing a few rows of the Pascal Triangle, which contains the binomial coefficients.

This one isn't tail-call recursive, and I can't for the life of me figure out how to make it so. Previous attempts produced incorrect values due to the integer division being performed too early.

 

[jedishrfu]

One function we wrote recursively was Ackermans function. Its a do nothing function but can really drag your machine down while doing a computation.

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

Here's the rosettacode.org Erlang version:

https://rosettacode.org/wiki/Pascal's_triangle#Erlang

[CODE lang="clike" title="pascal trianlge in erlang"]-import(lists).
-export([pascal/1]).

pascal(1)-> [[1]];
pascal(N) ->
L = pascal(N-1),
[H|_] = L,
[lists:zipwith(fun(X,Y)->X+Y end,[0]++H,H++[0])|L].[/CODE]

It looks like it has a tail recursion design.

 

[pbuk]

For some reason, the forum software wouldn't let me insert the code as text inside code tags,

I think there is something broken at the moment, there are other symptoms.

This one isn't tail-call recursive, and I can't for the life of me figure out how to make it so. Previous attempts produced incorrect values due to the integer division being performed too early.

Interesting, I would have thought the compiler could have sorted it out (perhaps there is a higher level of optimization you can select) but I think you need

  true ->
    (N * (N - 1)) div ((N - K) * K) * combi(N - 2, K - 1)

 

[pbuk]

Rosettacode has a different approach to binomial coeffecients using an explicit accumulator to make the tail recursion more obvious: https://rosettacode.org/wiki/Evaluate_binomial_coefficients#Erlang

 

[Mark44]

Interesting, I would have thought the compiler could have sorted it out (perhaps there is a higher level of optimization you can select) but I think you need

  true ->
    (N * (N - 1)) div ((N - K) * K) * combi(N - 2, K - 1)

I'm not familiar enough with the compiler and its settings to know if I can adjust this.

Regarding your suggestion, I actually tried that, but got incorrect results, due to integer division being performed at the wrong time. For example, for $~_5C_2$ the factor to the left of the call to combi() is
$$\frac{5 \cdot 4}{3 \cdot 2}= \frac {20} 6$$
With integer division, this works out to 3. The other factor, from the call to combi(), is $~_3C_1$ or 3, so the result would be 3 * 3 = 9.

If the factors are placed in the proper order, you get $20 \cdot 3 \text{ div } 6$, or 10, the correct value. I haven't run across any information about operator precedence an associativity, but it's almost certainly the case that multiplication and division are left-associative.