Recursion - do you use it in the real world?

[splin]

I agree with you. But do consider that we're talking about 80 bytes of stack space difference (on an ARM, only 30 on AVR (or 40 on Mega) which is small even when you've only got 1024 bytes to start with.

Well we clearly have very different opinions on what is 'small' in the context of an MCU with 1K of ram. 80 bytes of stack is 8% - for one trivial function - is a *huge* amount of one of the most valuable resources. Then double it if an interrupt routine were to print a number out - sure you probably wouldn't want to do this in a high priority interrupt routine but it would be perfectly legitimate to use it in a software interrupt such as a deferred low priority device driver handler routine. Then triple it if another lowish priority interrupt uses it.

Much worse if you are running an RTOS - now multiply that extra stack usage by the number of processes that can use that function. You'd likely want a processor with more than 1K of RAM with an RTOS but the principle remains that RAM costs money and is significantly more expensive than Flash.

Determining maximum stack usage is also much harder which is why recursion is banned by some codes of practice such as MISRA. The compiler can report the maximum stack used by a function but usually can't determine how many times a function can get called recursively. I'm sure there are some good tools available these days to help but stack sizing, especially in RTOS designs, was always something of a dark art and prone to errors - typically resulting in a hard to diagnose or reproduce crash.

Obviously its horses for courses and in some scenarios recursion may be justifiable by simpler code and thus potentially quicker to develop, more reliable and easier to maintain.

[sasa]

No body will persuade me that trivial: code + stack push + recursive call is faster than code +loop jump. It is simply impossible.

Well, perhaps more detailed analysis is in order.
...

No need realty and I will not comment anything particular...

What is evident here is that excuse for writing inappropriate code and using inappropriate methodology is based on a hope that complier will optimize it up to the level that wrong approach will result in good performance! And that is absurd!

The point of being good programmer is to write good optimized code which every compiler should  transfer into efficient machine code, even with zero optimization.  Compiler optimization should be only additional way to rewrite machine code to be efficient...

Several pages here is about tail recursion, compiler optimization, etc... It is simply irresponsible to rely on compiler optimization since on some other  platform may produce equally bad machine code as it is source code.

That is the whole point.

Towers of Hanoi is probably a good example - anyone want to turn this Hanoi code into an iterative version?

Towers of Hanoi is just an example for use of recursion, pointless math puzzle, with no practical usage than learning. Up to some small numbers of rods and disks it is possible to use iterative approach, but generally no.

As any recursion, it can be translated into iterative version, but that is equally pointless.

[NorthGuy]

I could do that, but then I'd split my recursive code into two functions (one for signed and one for unsigned, with one calling the other) to even things up and get both faster code and two useful functions for the price of one :-)

In all honesty, you cannot use the compiler bloat as an argument for or against recursion. I'm sure the -fstack-protector-all option would kill any chances for any recursion

There are many ways to make code faster. For example, you can unroll the loops.

Then the result depends a great deal on the typical data. For example, if most of the data consists of 9-10 digit numbers, it would pay off to divide by 10000000000 first, then by 1000000000 and continue downwards. This would avoid the need to reverse the array. But if the data consists of mostly smaller numbers, such approach would be a complete disaster.

As to the recursion, I think the tests confirmed what we knew all along:

- recursion doesn't produce any significant performance decrease
- the code is more compact and easier to write
- there's some extra stack usage, but it is typically not a problem

[sasa]

Does your C compiler insert the stack protector bloat in all the functions with local array as brucehoult's does? This certainly screws up the results to some extent.
...

I do not really care, that is based on brucehoult's code and I have sent complete source code. My choice will not be such testing case.

Let see brucehoult's testing results on his own test frame and other platforms.

[sasa]

You are forgetting that many modern compilers will do a tail call optimization and thus there is no stack push! (assuming arguments fit into registers) The entire recursive call is optimized away and replaced by a jump.

You certainly cannot rely on compilers optimization on every platform, as I have mentioned here several times. That is just excuse as any for inappropriate coding.

And brucehoult has demonstrated that even non tail-recursive function could be faster than iterative version - the overhead of the function call is simply less than the extra code that the non-recursive version needs.

Brucehoult demonstrated that only heavy machinery should be used, even to cover mouse hole... I'm certainly not a fan for that approach.

Assumptions are dangerous.

Very, very dangerous....

[janoc]

"assuming"? assuming or "hoping" compiler will do its magic is not a wise thing to do, from a programmer standpoint, imho... what if arguments are not fit in registers? "assuming" will create very minimal threat if you are working on a fixed familiar system everytime... but not when on many different systems...

Of course, if you are writing portable, multiplatform code, then what works on one system/compiler may not work on another.

However, in that case wasting few bytes or clock cycles is rarely your problem because you will need to deal with various abstractions to keep the code working between the different platforms. And those will likely cost you more than pushing few arguments on the stack.

Moreover, it is trivial to verify whether the optimization has, in fact, been done.

[janoc]

You certainly cannot rely on compilers optimization on every platform, as I have mentioned here several times. That is just excuse as any for inappropriate coding.

Where have I said that you should blindly rely on the optimization on every platform? That's a strawman you are fighting there.

On the other hand, when what you call "inappropriate coding" delivers both faster and smaller code (both very relevant on resource limited microcontrollers), then your argument flies out of the window. Should we not use the optimization when it is available only because you think such code is "inappropriate"?   

Heck, the code is even perfectly readable, if it was at least some convoluted hack like the Duff's device ...

Brucehoult demonstrated that only heavy machinery should be used, even to cover mouse hole... I'm certainly not a fan for that approach.

Again, that "heavy machinery" (not sure what is "heavy machinery" on a technique taught to every computer science/engineering freshman, but I digress) delivers better performance and needs less code space.

It doesn't mean I am going to start replacing my loops with recursion en masse, but it certainly debunks some widespread & incorrect assumptions.

Not being a fan of something simply isn't a good enough engineering argument here.

[Bruce Abbott]

Small PICs are fundamentally unsuited to running C code,

Which is why nobody writes code for small PICs in C.  Someone should tell Microchip!

The MCU executes machine code, not C. We use a high level language for convenience, not because it is more suited to a particular architecture. In fact translating C into something that works at all is not easy. But we push that problem onto the compiler writer - then we can blithely write 'elegant' source code, hoping that the compiler will optimize the mess it produces.

You are right though, 'small' PICs (and other MCUs which are similarly limited) are not suited to unrestricted recursion. That this is not considered a problem is proof that recursion is not a sought after feature on these chips, otherwise Microchip would have implemented it. But of course nobody uses 8 bit PICs anymore. Microchip must be a bunch of idiots - churning out new 8 bit PICs that nobody wants. 

[ehughes]

http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf


Most people who have to worry about their code working in a difficult scenario (say on a robot 2 million miles away) avoid recursion.

http://www.embedded.com/electronics-blogs/break-points/4025734/MISRA-minimizes-mishaps

MISRA -- > Rule 16.2: Functions shall not call themselves, either directly or indirectly.

[Cerebus]

http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf


Most people who have to worry about their code working in a difficult scenario (say on a robot 2 million miles away) avoid recursion.

http://www.embedded.com/electronics-blogs/break-points/4025734/MISRA-minimizes-mishaps

MISRA -- > Rule 16.2: Functions shall not call themselves, either directly or indirectly.

Argument by authority is never very convincing, especially when you cite as authority an agency whose most infamous coding error is splashed over the surface of Mars.

And here are some other rules from MISRA, quoted above.

Rule 2.2: Source code shall only use /* ... */ style comments.

Rule 20.4: Dynamic heap memory allocation shall not be used.

So, "thou shalt not use recursion" combined with "thou shalt not allocate memory" - presumably "thou shalt not compute any problem the size of which is not fully known in advance" and "when making lamentation about this in source code thou shalt only do so in /* ... */ comments", yerrse...

Judging from some of the other rules, like 5.2, I'm kind of surprised that MISRA doesn't have one that starts "code shall be punched on 80 column cards, starting in column 7...".

I find your citations to be, errm, somewhat underwhelmingly unconvincing.

[bd139]

Indeed. We have more cash moving through our software every *quarter* than the entire MER mission cost to date, the codebase is hundreds of times bigger and we could technically with one data leak screw most of the European finance sector. We don't use MISRA or JPL coding standards! 

Edit: you should be scared. We even have beer fridge in the office!

[tggzzz]

Indeed. We have more cash moving through our software every *quarter* than the entire MER mission cost to date, the codebase is hundreds of times bigger and we could technically with one data leak screw most of the European finance sector. We don't use MISRA or JPL coding standards! 

Edit: you should be scared. We even have beer fridge in the office!

I am scared (but not surprised) and not because you have  a beer fridge

[bd139]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

[tggzzz]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

Nah. It is the swallowed NullPointerExceptions and arithmetic errors, amongst many things.

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

[Cerebus]

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

Vacuum packed PG Tips. It'll be worth a fortune three months into the zombie apocalypse. And with a few jars of Vegemite you'll be able to command a veritable army of ex-pat Aussies.

[sasa]

Where have I said that you should blindly rely on the optimization on every platform? That's a strawman you are fighting there.

Certainly you are not computer software design nor engineer (sorry if you are). Your knowledge and experience may be quite limited and based on some specific university classes, or worst some third-party specific courses, or what you read elsewhere. If someone read that tail recursion is a fancy way of coding and can solve any possible problem - it should be done this way, since there is no negative effect over all, because compiler will optimize it for you... 

Quite superficial and pointless argumentation. Did you ask yourself why exists so many other ways? Main principle in programming is to solve problem on the most efficient and stable way. And using tail recursion for every trivial task is certainly inappropriate and irresponsible. It is the same in EE, you do not use FPGA just to blink led... Oh, but digression is obvious - FPGA is so fancy! It does not matter it is expensive and require quite logistic on the board.

Quite obvious it is pointless discussion - do it at inappropriate way if you want, even in medical devices, planes or nuclear plants and plays with other lives...

Most of people here use programming in C as a necessary evil in order just that whole damn thing start  to work, knowing no better ways than use tail recursion in every occasion. 

Did you even seen how percentage my iterative solution converting integer to string is faster and how code is simple. It also have no single negative effect and can be used with any small MCU as well. Obviously, it is pointless discussion with people knowing nothing more suitable than tail recursion. 

Sapienti sat.

[westfw]

What is evident here is that excuse for writing inappropriate code and using inappropriate methodology is based on a hope that complier will optimize it up to the level that wrong approach will result in good performance! And that is absurd!

The point of being good programmer is to write good optimized code which every compiler should  transfer into efficient machine code, even with zero optimization.

I disagree with you almost 100%.  If you deign to use a compiler, you are ALWAYS counting on it to optimize enough to yield good performance, and many times so with any modern language that isn't tightly coupled the CPU architecture of the target (people will tell you that C is a fancy assembler for the PDP-11.  That's pretty close, but the days where you carefully pick which local variables go into registers and use --p and p++ because they produce more efficient code with the available instruction set are long gone (and good riddance!)  And it's not like we're asking for "extreme optimization" in order to allow simple recursion to be "somewhat efficient."  It's just "don't put lots more data on the stack than you really need to."

Also, perhaps you haven't used an old compiler or one that really does "zero optimization", or taken a compiler design class.  What comes out of most compilers with "no optimization at all" is REALLY AWFUL.  (hint: "gcc -O0" does not do "zero optimization."  For a while, the "free" PIC-8 compiler that Microchip was distributing really did zero optimization, and people were horrified - sure that they were intentionally de-optimizing the code.  I believe they've relented, and now offer something closer to gcc's -O0.  You might be able to find examples from that era in archives around the net.)

BTW, there's at least one C compiler for PIC18 that supports recursion (they implement a second stack for data), and several AVR compilers use separate "data stack" and "return stack.)  FORTH usually has separate call and data stacks.  Many architectures can use essentially any register as a stack pointer, except for interrupts.   So having a "hardware return stack" (not in normal memory) doesn't preclude recursion.

[westfw]

BTW, we're not in the 1970s.  There ought to be lots of well-researched, well-implemented and standardized, well-understood, well-analyzed and well-measured recursive algorithms.  I mean, ALL recursive algorithms are supposed to have nice, bounded termination conditions, and most of the bugs that led to stack exhaustion should be gone (not that you can't write your own!)   I'd expect that the stack usage of the, say, the C++ STL implementation of red/black trees (which I assume is recursive) is better-analyzed than the stack usage of printf().  (OTOH, perhaps all STL code is carefully written to avoid recursion?)

[sasa]

For a while, the "free" PIC-8 compiler that Microchip was distributing really did zero optimization, and people were horrified - sure that they were intentionally de-optimizing the code. 

This have nothing related with  "zero optimization" note. I used to use XC8 years ago, it is based on   HI-TECH C compiler which had exactly the same limitation in free license mode. They intentionally inserted useless instructions and loops in order to force people to buy commercial license, regardless what Microchip representatives explains on they forum...

I will not comment anything else, it is simply pointless.

[bd139]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

Nah. It is the swallowed NullPointerExceptions and arithmetic errors, amongst many things.

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

We haven't had an NPE for years as we have very heavy levels of assertions. Input, outputs, invariants, the lot. Arithmetic errors are a problem, particularly when one your suppliers sends financial values through their APIs as floats!?!?

All I need is ASDA beans and tea bags. Oh and a tin opener. Adding to list

[tggzzz]

It's the outsourcing that scares me.

I'm going to start digging a bunker in the garden this weekend. It'll be either the outsourcers or the recursion that causes satellites and financial ruin to rain down on us.

Nah. It is the swallowed NullPointerExceptions and arithmetic errors, amongst many things.

Will the bunker be big enough to contain all your valuables ;} And are they stored as Soveriegns/Britannias, or in EUR?

We haven't had an NPE for years as we have very heavy levels of assertions. Input, outputs, invariants, the lot. Arithmetic errors are a problem, particularly when one your suppliers sends financial values through their APIs as floats!?!?

All I need is ASDA beans and tea bags. Oh and a tin opener. Adding to list

That's the way it should be, of course - but I have seen otherwise My comments were ignored due to corporate culture; I left.

As for other suppliers being idiotic, well "reconciliation" is a whole subfield of banking transactions.

In a different existence, I created low-impact instrumentation and insisted it was left in delivered products. It was very pleasing to see how many inter-company battles were throttled before people even thought about bringing in lawyers

[bd139]

Indeed. I've not renewed a few contracts over crazy like that. The worst is the cargo cults. They are confident that they are doing it right and are waving their hands approximately but the work they have done is ineffective, solves no problems and costs a lot of money.

Agree with instrumentation. We are VERY instrumentation heavy. About 20% of our infrastructure is monitoring, tracing and alerting. We find and fix the defects that do exist pretty much instantly. It's nice to get a call from a client and you tell them that the issue was fixed two hours before they called. Everyone goes away happy.

[Cerebus]

... The worst is the cargo cults. ...

Or anywhere where you can play "programming buzzword-du-jour bingo".

Run a project like that anywhere near me and you have to be Agile to avoid ASSERT(BacksideStatus == HeavilyBooted).

[janoc]

Where have I said that you should blindly rely on the optimization on every platform? That's a strawman you are fighting there.

Certainly you are not computer software design nor engineer (sorry if you are). Your knowledge and experience may be quite limited and based on some specific university classes, or worst some third-party specific courses, or what you read elsewhere. If someone read that tail recursion is a fancy way of coding and can solve any possible problem - it should be done this way, since there is no negative effect over all, because compiler will optimize it for you... 

Sasa, will all respect, your assumptions are getting worse and worse. 20 years of software engineering under my belt, both commercial (including some embedded work) and research. I guess that's not enough and I am obviously not knowing what am I doing. Thank you for telling me!

Quite superficial and pointless argumentation. Did you ask yourself why exists so many other ways? Main principle in programming is to solve problem on the most efficient and stable way. And using tail recursion for every trivial task is certainly inappropriate and irresponsible. It is the same in EE, you do not use FPGA just to blink led... Oh, but digression is obvious - FPGA is so fancy! It does not matter it is expensive and require quite logistic on the board.

You are still fighting strawmen here, because nobody has made this argument. Nobody is advocating mindlessly using one technique over the other, but you seem to be constantly missing the point.

Quite obvious it is pointless discussion - do it at inappropriate way if you want, even in medical devices, planes or nuclear plants and plays with other lives...

Most of people here use programming in C as a necessary evil in order just that whole damn thing start  to work, knowing no better ways than use tail recursion in every occasion. 

Sorry, that's complete BS - nobody was making such argument here. Another strawman.

Did you even seen how percentage my iterative solution converting integer to string is faster and how code is simple. It also have no single negative effect and can be used with any small MCU as well.

Sapienti sat.

Well, the facts don't seem to support neither the "faster" and the "simple" is arguable (granted, it is trivial code in both cases).

Obviously, it is pointless discussion with people knowing nothing more suitable than tail recursion. 

No, it is a completely pointless discussion with people not understanding (or willing to understand) written text and not wanting to see facts even when they get them on a silver plate.

Sorry.

[Mechatrommer]

so this is a dick waving contest of how many years of black belt you have... well, i have about 20 years of "self-learnt" belt, anything other than assembly language for performance is moot, and thats it...  if you really care about squeezing out performance by tweaking generated machine code, reducing "backstage" housekeeping code generated by the compiler, then i think you should rethink of your life... gurus in algorithm are only talking about O(?) operations, not in anywhere mentioning about machine specific code, let alone compiler options. yeah, i have to specifically key in the -ffunction-sections, -Wl,--gc-sections options in every AVR-GCC projects that i built, just to get rid of dormant functions in the final hex file, fucking compilers of the 21st century... and that compiler options only available when you ask in the forum  and err (edit), havent i told you one of my PIC16 program went rampant just because of stack overflow? i called to many functions.. fucking compiler for not letting me know..