• #26
.Scott
Homework Helper
2,536
914
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
 
  • Informative
Likes anorlunda
  • #27
DavidSnider
Gold Member
487
131
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.
 
  • #28
Klystron
Gold Member
690
939
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 sytems 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.
 
  • Like
Likes anorlunda
  • #29
537
153
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.
 
Last edited:
  • #30
rcgldr
Homework Helper
8,693
523
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.
 
Last edited:
  • Like
Likes QuantumQuest, bhobba and Klystron
  • #31
11,827
5,450
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.
 
  • Like
  • Informative
Likes DrClaude, QuantumQuest, bhobba and 1 other person
  • #32
Klystron
Gold Member
690
939
[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.
 
  • Like
  • Informative
Likes DrClaude, QuantumQuest and jedishrfu
  • #33
9,438
2,489
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
 
  • Like
Likes Klystron and QuantumQuest
  • #34
rcgldr
Homework Helper
8,693
523
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.
 
Last edited:
  • #35
11,827
5,450
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.
 
  • #36
.Scott
Homework Helper
2,536
914
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:
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.
 
  • Like
Likes bhobba, jedishrfu and Greg Bernhardt
  • #37
.Scott
Homework Helper
2,536
914
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.



ZigZag.png



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.
 
  • #38
11,827
5,450
Zig-zag bah! I shall name it the Mark of Zorro!
 
  • Like
Likes bhobba
  • #39
.Scott
Homework Helper
2,536
914
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.
 
  • Haha
Likes jedishrfu
  • #40
.Scott
Homework Helper
2,536
914
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.
 
  • #41
Stephen Tashi
Science Advisor
7,183
1,316
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.
 
  • #42
rcgldr
Homework Helper
8,693
523
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.
 
  • Informative
Likes DrClaude

Related Threads on Recursion in Programming and When to Use or Not to Use It

  • Last Post
Replies
9
Views
3K
Replies
2
Views
689
Replies
39
Views
2K
Replies
4
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
17K
  • Last Post
Replies
12
Views
80K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
13
Views
886
Top