Recursion - do you use it in the real world?

[Cerebus]

The Power of 10: Rules for Developing Safety-Critical Code

1. Avoid complex flow constructs, such as goto and recursion.

The NASA study of the Toyota Electronic throttle control firmware found at least 243 violations of these rules.

Good point Bruce. But the fact is, that here seems no body works for NASA or at least on sensitive and safety-critical software, I have pointed already in this thread.

I don't get the obsession some people have with NASA as a touchstone. Most of their flight prototypes went KABOOM the first time they were switched on and, as I have previously pointed out, their most infamous programming bug is splattered across the surface of Mars. 

I never programmed for NASA, but I used to have two people working alongside me (Doing AI in FORTRAN, don't ask!) who were moonlighting from their day jobs as programmers at JPL. Their code was nothing to be proud of and quite enough to convince me that there's nothing special about the staff at NASA, they're just as crappy as everybody else.

[Mechatrommer]

The Power of 10: Rules for Developing Safety-Critical Code

1. Avoid complex flow constructs, such as goto and recursion.

The NASA study of the Toyota Electronic throttle control firmware found at least 243 violations of these rules.

Toyota used a tool called gstack from Green Hills Software to determine maximum stack size requirements. The tool gstack is a static analyzer that computes an upper bound on the stack size required by a given executable. For the ETCS-i, it reported the maximum possible stack size as 1688 bytes. This result comes with a caveat, however: gstack cannot account for recursion, as stated in its user manual:

gstack cannot work if there are potential direct or indirect recursive calls in the program because it cannot predict how many times the recursion can occur. gstack prints a warning message if it detects a possible recursion in the call graph.

Faced with this limitation, Toyota added an extra margin of safety to the predicted bound by allocating 4096 bytes for the ETCS-i stack—more than double the original prediction. As to why recursion was present in the ETCS-i software, Toyota reported that it was a deliberate design choice in order to simplify the quality assurance process and reduce the total size of the executable...

The flow reveals that the function is actually doubly recursive: It flows from gehdlp_req_1ms to function2, recurses back to function2, and then recurses again back to gehdlp_req_1ms. Toyota engineers confirmed this software recursion. It is not clear what impact recursion has with respect to the larger UA problem. Whether one recursive loop or two, there are other sites of recursion in the ETCS-i that remain unanalyzed.

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

[NorthGuy]

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

If you simplify it a bit, your code will be perfectly suitable for tail recursion optimization 

Code: [Select]

void goinsideme(int depth) {
  if (depth < whatever) {
    goinsideme(depth+1);
  } else {
    tellmymomma();
  }
}

[splin]

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

AutoLandingSystem::AdjustFlightPath(int Altitude, int AirSpeed, int DescentRate, int Thrust, int Pitch)
{
      //Todo: Make sure Flight Manual notes that behaviour is unspecified if altitude exceeds 32767 feet

      if(++RecursionLevel >= MAX_RECURSION_LEVEL)
             throw(TIME_TO_SAY_YOUR_PRAYERS_EXCEPTION);

      //Compute best Landing vector - variables interact so adjust parameters and recompute until error is within bounds
      if(CalcPathError(Altitude, AirSpeed, DescentRate, Thrust, Pitch) > MAX_PATH_ERROR)
              AdjustFlightPath(Altitude, AdjustAirSpeed(AirSpeed), DescentRate, Thrust, Pitch);
     ...

}

[Mechatrommer]

If you simplify it a bit, your code will be perfectly suitable for tail recursion optimization 

yup except it does nothing other than goinsideme, for obvious reason (to get to the point)... tail this...

Code: [Select]


Public Sub QuickSort(a() As Integer, Start As Long, Finish As Long)
    Dim posOfSplitter As Long

    If Finish > Start Then
        Partition a(), Start, Finish, posOfSplitter
        QuickSort a(), Start, posOfSplitter - 1
        QuickSort a(), posOfSplitter + 1, Finish
    End If
End Sub

;Partition() excluded for obvious reason...


AutoLandingSystem::AdjustFlightPath(int Altitude, int AirSpeed, int DescentRate, int Thrust, int Pitch)
{
      //Todo: Make sure Flight Manual notes that behaviour is unspecified if altitude exceeds 32767 feet

      if(++RecursionLevel >= MAX_RECURSION_LEVEL)
             throw(TIME_TO_SAY_YOUR_PRAYERS_EXCEPTION);

      //Compute best Landing vector - variables interact so adjust parameters and recompute until error is within bounds
      if(CalcPathError(Altitude, AirSpeed, DescentRate, Thrust, Pitch) > MAX_PATH_ERROR)
              AdjustFlightPath(Altitude, AdjustAirSpeed(AirSpeed), DescentRate, Thrust, Pitch);
     ...

}

thats why you should not be in avionics business... imho...

[Bruce Abbott]

I don't get the obsession some people have with NASA as a touchstone. Most of their flight prototypes went KABOOM the first time they were switched on and, as I have previously pointed out, their most infamous programming bug is splattered across the surface of Mars.

Not a 'touchstone', but experience we can benefit from. They have learned expensive lessons the hard way.

As (hopefully) did Toyota. Perhaps there was no fault in their code and all the incidents of 'unintended acceleration' were due to user error, but the lawsuit brought to light their unsafe coding practices. Their stack checking tool warned them that it could not account for recursion, so what did they do? Fudged the stack size based on nothing more than pure guesswork. And why did they use recursion? Not because it was the obvious algorithm for the job, but because they were trying to save program memory. They created spaghetti code to save a few bucks, and ended up costing the company billions (and perhaps even killing a few people).       

Toyota's software engineers must have thought they were such awesome coders that the rules didn't apply to them. Maybe they were that awesome, but their code cannot be verified so we will never know if it was safe. That's simply irresponsible, and indefensible.
 

I used to have two people working alongside me (Doing AI in FORTRAN, don't ask!) who were moonlighting from their day jobs as programmers at JPL. Their code was nothing to be proud of and quite enough to convince me that there's nothing special about the staff at NASA, they're just as crappy as everybody else.

NASA needs these rules because their programmers are 'just as crappy as everybody else'. I am not arrogant enough to think that I am better than NASA. Are you?
   

[Bruce Abbott]

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities...

You better have something like that, or your code is totally unsafe. But even with it, how do you know how much stack will be used? What about when someone modifies the code without re-calculating it? What if the counter is not properly initialized, or gets corrupted? Can your tools detect these issues? If not then the code is still unsafe.

[Cerebus]

I am not arrogant enough to think that I am better than NASA. Are you?   

Of course I am better than NASA. They are a soulless US federal agency, I am a warm fuzzy human being. 

I suspect the real touchstones for software quality are people we don't even notice, because they just quietly produce stuff that works.

[Mr. Scram]

the depth of recursion can easily be monitored or limited by

Code: [Select]

void goinsideme(int &depth) {
if (depth < whatever) {
depth++;
goinsideme(depth);
depth--;
} else {
tellmymomma();
};
};

no need fancy and expensive utilities... opps, i forgot this thread is about optimizing tail recursion, sorry. cant help you with that then ...

I applied almost exactly that solution. Combined with the fact that the recursion occurred in one specific spot, all was well.

[westfw]

I am not arrogant enough to think that I am better than NASA. Are you?

Did you SEE the code that led to Ariane blowing up?  Where they made their Ada look like Fortran, and redefined "int64" to be a 32bit integer (or something like that)?  (Ok, ESA rather than NASA, but still...)  I'm sure NASA has some very good Fortran programmers, and I'm equally sure that some of their code still looks like Fortran.  (No recursion, no  dynamic allocation.  Perfect!)

[depth checks] You better have something like that, or your code is totally unsafe.

You should totally put limit counts on your iterative loops too!  Which is semi-serious.  I actually had that bug once.)
Seriously: there are well-understood recursive algorithms with well defined depth that shouldn't need additional paranoia.  Our sample printDec() doesn't need a depth check.  Making up an entirely new recursive algorithm is another matter entirely.

[Mechatrommer]

alas i dont think depth check is good enough. its only for catashrophe prevention, not the integrity of the running program. program code should work to its completion imho, if somehow limitation should be imposed on the recursive function, then another strategies should be used such as limiting or divide and conquer the data size to be put into the function, or use equivalent iterative code. as an example of the quick sort above, if depth limitation is activated, the data will not be fully sorted. so, as most wise people said, use it when appropriate vice versa...

no need fancy and expensive utilities...

You better have something like that, or your code is totally unsafe. But even with it, how do you know how much stack will be used? What about when someone modifies the code without re-calculating it? What if the counter is not properly initialized, or gets corrupted? Can your tools detect these issues? If not then the code is still unsafe.

thats why, if its a concern to use recursion in limited resource system, then its better not to use it... if its inevitable, then it need to be tested and the extensiveness of the test will depend on the risk involved, this is where experience and competency come in... ymmv.

[sasa]

You should totally put limit counts on your iterative loops too!  Which is semi-serious. 

Not quite always.

If algorithm is stable, you always know or you can predict almost good enough how much at maximum memory and time you would need for execution, depending on all possible inputs.

If algorithm is not stable - praying that worst case scenario never happens is the best you can do, regardless it is iterative or recursive solution. With recursion you may just hit the roof much faster...

Hopefully, there is many different algorithms in theory and practice...

And BTW, you can count to hit the roof even with stable recursion based algorithm as our small example here is, if use it extensively in  multi-core/multi-thread environment, as someone already mentioned (I think it was user splin).

[brucehoult]

alas i dont think depth check is good enough. its only for catashrophe prevention, not the integrity of the running program. program code should work to its completion imho, if somehow limitation should be imposed on the recursive function, then another strategies should be used such as limiting or divide and conquer the data size to be put into the function, or use equivalent iterative code. as an example of the quick sort above, if depth limitation is activated, the data will not be fully sorted. so, as most wise people said, use it when appropriate vice versa...

That quicksort code was dumb. A small fix makes it safe (with tail call optimization)

Code: [Select]

Public Sub QuickSort(a() As Integer, Start As Long, Finish As Long)
    Dim posOfSplitter As Long

    If Finish > Start Then
        Partition a(), Start, Finish, posOfSplitter
        If posOfSplitter-Start < Finish-posOfSplitter Then
            QuickSort a(), Start, posOfSplitter - 1
            QuickSort a(), posOfSplitter + 1, Finish
        Else
            QuickSort a(), posOfSplitter + 1, Finish
            QuickSort a(), Start, posOfSplitter - 1
        End If
    End If
End Sub

This is guaranteed to use stack less than log2(Finish-Start). Even for a billion items that's no more than 30 levels of recursion i.e. probably less than 1 KB of stack.

[sasa]

This is how I would make basic test app and that is added - I have no more time nor any interest to improve this further.

- Proper testing data distribution over whole range, or range of interest, instead of max 8 decimal digits.

- Proper testings excluding the best and the worst result and giving the mean of the rest.  In real testing case I would add standard deviation information as well, better elapsed time resolution  than ms, but it is anyway a bit better now...

- Possibility to compile and run on embedded systems.

- Added hamster_nz function (sorry, I missed it). Classical example, really fast with many optimization parameters.

- Brucehoult code is disabled, as it missing data pointer and returning pointer(similar to itoc). You may correct it accordingly and add it for testings if you wish.

- Janoc's function is adopted only to return null-terminator pointer in resulted string, in order to be identical to the proposed prototype function (faster writing new converted numbers).

Results are still similar:

O0:

Code: [Select]

itoc_sasa_1       : 2022.00ms Eliminated 2022, 2023 from 5 results
itoc_hamster_nz_1 : 2707.00ms Eliminated 2707, 2708 from 5 results
itoc_NorthGuy_1   : 2959.00ms Eliminated 2959, 2960 from 5 results
itoc_janoc_1      : 3591.00ms Eliminated 3591, 3592 from 5 results

O:

Code: [Select]

itoc_sasa_1       :  879.00ms Eliminated 878, 879 from 5 results
itoc_NorthGuy_1   : 1569.33ms Eliminated 1569, 1570 from 5 results
itoc_hamster_nz_1 : 1695.00ms Eliminated 1695, 1696 from 5 results
itoc_janoc_1      : 1820.67ms Eliminated 1820, 1823 from 5 results

O2:

Code: [Select]

itoc_sasa_1       :  888.00ms Eliminated 888, 888 from 5 results
itoc_janoc_1      : 1053.33ms Eliminated 1053, 1054 from 5 results
itoc_NorthGuy_1   : 1422.00ms Eliminated 1421, 1423 from 5 results
itoc_hamster_nz_1 : 1515.67ms Eliminated 1515, 1516 from 5 results

Os:

Code: [Select]

itoc_sasa_1       : 2175.33ms Eliminated 2175, 2177 from 5 results
itoc_hamster_nz_1 : 3052.00ms Eliminated 3052, 3052 from 5 results
itoc_janoc_1      : 3059.67ms Eliminated 3059, 3060 from 5 results
itoc_NorthGuy_1   : 3087.00ms Eliminated 3086, 3087 from 5 results

Ofast:

Code: [Select]

itoc_sasa_1       :  826.67ms Eliminated 826, 828 from 5 results
itoc_janoc_1      :  951.33ms Eliminated 951, 952 from 5 results
itoc_hamster_nz_1 : 1296.00ms Eliminated 1295, 1297 from 5 results
itoc_NorthGuy_1   : 1422.00ms Eliminated 1422, 1422 from 5 results


[Cerebus]

Go is Algol 68 in a shirt and tie. The shirt has pizza stains down it but you still wear it in a nightclub because the lights are down. It's also an acknowledgement that C was a silly idea all along as it was written by two toked up hippies on an ASR33 and PDP8 trying to write games and accidentally ending up with an OS and compiler and now we need to be serious because the CVE list is make it look like it was a bad idea.

I hope they have "use after free" chiseled on their gravestones.

I finally got a few minutes free and simultaneously remembered that you'd pointed me at go. Both have happened in the last few days, but not together. So I took a look.

Code: [Select]

PROC my conclusion = () VOID:
BEGIN
    PROC i will eat my hat = () VOID: CODE () "Om, nom, nom"; {Algol68RS extension: Assembly code for a theoretical hat eating processor.}

    BOOL go is the new algol 68 = FALSE; {Algol 68 aficionados will appreciate that the mode here is BOOL, not REF BOOL.}

    IF go is the new algol 68 THEN i will eat my hat FI
END

{That ought to be runnable, as long as you've got a HatEater9000 to run it on, but it's been a while since I actually had to feed any Algol 68 into a compiler.}

Not really close, not even first cousins, second or third - maybe.

It's got some merits, but it lacks the rigour and orthogonality that I always found so aesthetically pleasing in Algol 68 and the ultra clean syntax and, last but not least, the option to put (non-significant) spaces in variable names.

Thanks for the heads up anyway.

[Howardlong]

FWIW, my first recursive program was in Algol 60, keyed in on paper tape. It was a key feature that everyone talked about, but mostly failed to find a use for beyond the Fibonacci sequence or calculating factorials. It was quite a key facet of programmer training.

Almost all of my recursion use nowadays isn't a new type of implementation, it's to workaround limitations of a one particular language which architecturally doesn't lend itself well to iterating as it's predominantly set-based. It also makes for excruciatingly difficult code to read, understand and maintain, it's like a stylus coming off a record when you come across it in a peer review. It's a reasonable solution in certain situations given the language limitations, but it's just hard to comprehend when figuring out how it works and any potential problems or limitations it may have in a given use case.

[tggzzz]

FWIW, my first recursive program was in Algol 60, keyed in on paper tape. It was a key feature that everyone talked about, but mostly failed to find a use for beyond the Fibonacci sequence or calculating factorials. It was quite a key facet of programmer training.

Elliott Algol?

Famously Hoare implemented the compiler in 4Kwords (The 803 had an architectural max of 8K) using  a "collection of mutually recursive procedures" using "an explicit stack for recursion". He noted that "Without the Algol 60 concept of recursion, at that time highly controversial, we could not have written this compiler at all".

The 4K/8K  limit should cause those that claim recursion is (without qualification) too complex/inefficient/slow to reconsider their claims.

[bd139]

Go is Algol 68 in a shirt and tie. The shirt has pizza stains down it but you still wear it in a nightclub because the lights are down. It's also an acknowledgement that C was a silly idea all along as it was written by two toked up hippies on an ASR33 and PDP8 trying to write games and accidentally ending up with an OS and compiler and now we need to be serious because the CVE list is make it look like it was a bad idea.

I hope they have "use after free" chiseled on their gravestones.

I finally got a few minutes free and simultaneously remembered that you'd pointed me at go. Both have happened in the last few days, but not together. So I took a look.

Code: [Select]

PROC my conclusion = () VOID:
BEGIN
    PROC i will eat my hat = () VOID: CODE () "Om, nom, nom"; {Algol68RS extension: Assembly code for a theoretical hat eating processor.}

    BOOL go is the new algol 68 = FALSE; {Algol 68 aficionados will appreciate that the mode here is BOOL, not REF BOOL.}

    IF go is the new algol 68 THEN i will eat my hat FI
END

{That ought to be runnable, as long as you've got a HatEater9000 to run it on, but it's been a while since I actually had to feed any Algol 68 into a compiler.}

Not really close, not even first cousins, second or third - maybe.

It's got some merits, but it lacks the rigour and orthogonality that I always found so aesthetically pleasing in Algol 68 and the ultra clean syntax and, last but not least, the option to put (non-significant) spaces in variable names.

Thanks for the heads up anyway.

A detailed comparison...

https://cowlark.com/2009-11-15-go/

[Howardlong]

FWIW, my first recursive program was in Algol 60, keyed in on paper tape. It was a key feature that everyone talked about, but mostly failed to find a use for beyond the Fibonacci sequence or calculating factorials. It was quite a key facet of programmer training.

Elliott Algol?

Famously Hoare implemented the compiler in 4Kwords (The 803 had an architectural max of 8K) using  a "collection of mutually recursive procedures" using "an explicit stack for recursion". He noted that "Without the Algol 60 concept of recursion, at that time highly controversial, we could not have written this compiler at all".

The 4K/8K  limit should cause those that claim recursion is (without qualification) too complex/inefficient/slow to reconsider their claims.

... but those weren't just any words, they were 39 bit words!

The modifier bit was pretty interesting, allowing not only for indirect addressing, but also self-modifying code, used to great effect in the initial instructions.

[sasa]

What is evident is that everyone forced recursion for this integer to string example, gave up after pages and page "proves by testing" that code is faster and compact...

After making real testing values and measuring in proper environment, naturally no one have any further argument to disprove obvious. Perhaps it would be probably "smaller and cleaner" with C interpreter, however compiled, pointer arithmetic and iterative approach is more "natural way" and faster to CPU to execute some simple tasks as this one...

Pretty much waste of time in this thread.

[NorthGuy]

Pretty much waste of time in this thread.

I though the question was not whether it is possible to write a code which executes faster. It is certainly possible to do so without recursion, and it will be even faster if you don't use C at all.

However, the question was whether the recursive code is somehow slower than essentially the same code without recursion. The tests made by brucehoult have proven that the speed is about the same. The result was partly confounded by the fact that the compiler added piles of stack-checking bloat to the non-recursive code, but brucehoult argued that C does what it does and removing the stack bloat would be tweaking. And I agree with that - if you use C you've got to accept the consequences be it bloat  or optimization. But even if brucehoult repeated the tests without bloat, I doubt that the difference would be large. The conclusion would stay.

Your results confirmed this. We didn't see the disassembly, so there's no way to tell what the C compiler did in this case, but your code came remarkably close to most similar version of recursive code posted by janoc both in his and your tests when optimized for speed.

Do you not agree with that conclusion?

[westfw]

everyone forced recursion for this integer to string example, gave up after pages and page "proves by testing" that code is faster and compact...

That's because you were the only one focused on proving "faster and more compact."  Everyone else was content to say "hey, this low-effort recursive implementation was 1) not awful, and 2) actually turned out faster and more compact than that other low-effort iterative implementation.  Also, you switched from "embedded microcontrollers" to x86, which for some reason seems to do a particularly poor job of optimizing this algorithm - and you're correct that if you have to start hunting for special compile switches then it's not worth it.

My (very old - 8088 days, and pre-C compilers) recursive x86 decout looked like:

Code: [Select]

public decout
ten    dw    10
decout    proc near  ;; enter with 16bit value in ax
    xor    dx,dx
    div    ten
    push    dx
    or    ax,ax
    jz    DECOU2
    call    decout
decou2:    pop    ax
    add    al,'0'
    call    typchr
    ret
decout    endp

[sasa]

...
Do you not agree with that conclusion?

Test case provided by brucehoult is definitely wrong.

Results prove only one - good algorithm should never depend on compiler optimization. That is said already many times. As well, this as well imply that results on embedded platform cannot be much different.

I have no time for extensive testings, but compiling with AVR show that janoc's recursive solution is worst 2x in size + stack usage (did not manage to test speed).

BTW. You have made function with infinite loop and continue with finite data - that (and use of labels and goto) are basic examples how code in structured programming should never be written.

@brucehoult You may thanks to anyone many times you want to fight your own lost battles. But at least provide tests in fair conditions and brings fair conclusions next time. At end, never mind, unless your code and suggestion does not cost someone life, health or money...

[NorthGuy]

Results prove only one - good algorithm should never depend on compiler optimization.

I agree. You cannot rely on particular optimization or anything of that sort simply because it may be gone in future versions. However, I don't think this can be proven or disproven. Without a doubt, measuring speed of anything cannot be used as a proof of this statement.

BTW. You have made function with infinite loop and continue with finite data - that (and use of labels and goto) are basic examples how code in structured programming should never be written.

Why? I like using "break" and "continue". It saves lots of time. In this particular loop it doesn't matter, but in some more complex loops, getting out of the loop prematurely with "break" (or eliminating part of the processing with "continue") is very handy. Otherwise, you get lots of nested ifs which are much more messy.

[hamster_nz]

Results prove only one - good algorithm should never depend on compiler optimization.

I agree. You cannot rely on particular optimization or anything of that sort simply because it may be gone in future versions. However, I don't think this can be proven or disproven. Without a doubt, measuring speed of anything cannot be used as a proof of this statement.

BTW. You have made function with infinite loop and continue with finite data - that (and use of labels and goto) are basic examples how code in structured programming should never be written.

Why? I like using "break" and "continue". It saves lots of time.

I find that 'continue' and 'break' are quite agreeable.

I also find goto's are agreeable to handle complex exceptional conditionals - where you might need to free file handles and release memory and so on. I just don't like them so much if the jump out of inner loops.

I don't find this example particularly distasteful in any way:

Code: [Select]

void func(char filename, int buffer_size)
   FILE *file = NULL;
   void *buffer = NULL;

   file = fopen(filename,"rb")
   if(file == NULL) goto error_cleanup;

   buffer = malloc(buffer_size);
   if(buffer == NULL) goto error_cleanup;

   while(1) {
      if(!read_a_record(file, buffer))
        break;
      if(!record_matches(buffer))
       continue
     do_stuff_with_matching_records(buffer);
   }

   free(buffer);
   fclose(file);
   return SUCCESS;

error_cleanup:
   if(buffer != NULL)  free(buffer);
   if(file != NULL)    fclose(file)
   return FAILURE;
}