Recursion - do you use it in the real world?

[westfw]

There are some algorithms that become extremely cleanly expressed when you use recursion.  Anything based on trees or graphs, for example.

I "grew up" with factorial, Towers of Hanoi, and maybe sort, as example recursive jobs, and I never really understood what was the point.  Then, much more recently, I took a modern class in algorithms that covered tree algorithms (that didn't EXIST when I was in school!) and had one of those "ah hah!" moments where recursion suddenly made a lot more sense.

Now, most of us here are EE types and write pretty deeply embedded code.  In fact, we don't often come across cases that benefit much from the sort of algorithms that recursion makes easier - A typical microcontroller with 128k of RAM can bubble-sort or linear search any possibly-contained set of data in reasonable time.  Work on something like a packet router with tens of thousands of routes (and enough memory not to worry about THAT restriction), and you start to worry about finding those N*log(N) algorithms instead of the N² (or worse algorithm.)  And that "log(n)" part typically comes from something that can be implemented with recursion...  (after a ~35y career, I had the somewhat depressing realization that I had spent nearly all of it improving the implementation of algorithms, or finessing my way around them, rather than developing BETTER algorithms.  Not "Computer Science" at all, really...)  (Heh.  I took another class recently that pointed out  that using the simple recursive algorithm to generate tables of Fibonacci numbers or Factorials is particularly silly, because you're constantly re-calculating intermediate numbers that you've already calculated.)

Now, A well-designed embedded program will keep careful track of recursion depth and resource consumption.  Or use algorithms that are well bounded and understood.  (I used to like a recusive decimal output function, even on moderately small systems.  And using some form of recursion for parsing user input is very common...)

[brucehoult]

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

That looks more like part of an entry in the Obfuscated C Contest.

Simple C, unchanged in 40 years. Which part do you not approve of?

For a start, it violates my rule that you shouldn't have to know, with certainty, the operator precedences to be able to understand what a line of code does. If you're going to write a line of code like that, at least throw some brackets in so that: 1) a human will understand it, 2) the compiler will do what you intend if you've mis-remembered an operator precedence.

I'd say something is pretty wrong with your understanding of C if you don't know that ?: is lower precedence than everything except assignment operators. C is the simplest language out there. Learn it!

Also, just on a correctness issue, what happens if the condition (right > end) is true? Hint: there's a reason C has a || operator as well as a | operator.

Yes, and the other version of the code a few lines below (which I didn't post) uses || and arrays. This version is to demonstrate that the speed is the same in either case.

Either | or || will work in this case, as there are no side effects, and in fact the compiler will freely convert between them depending on how cheap a conditional branch is, and whether the instruction set has a convenient "set boolean based on compare" instruction. As we already tested that left points inside the array, right can be no more than one past the end (and then only if the array has odd size). The caller makes sure the array is (at least) one bigger than actually required, so all is well.

Moreover, if you're going to do pointer arithmetic, as you do two lines above, sprinkle a few sizeof()s around or your code will crash and burn hard on the first machine it hits that doesn't agree with your assumptions on word size (which in this case appears to be (sizeof(int) == 1)).

You misunderstand C. Subtracting two pointers returns an integer of the number of *objects* between them (ints in this case) not the number of bytes between them. Adding an integer to a pointer multiplies the integer by the size of objects the pointer points to first.

The code is perfectly correct and safe C.

[brucehoult]

Now, A well-designed embedded program will keep careful track of recursion depth and resource consumption.  Or use algorithms that are well bounded and understood.  (I used to like a recusive decimal output function, even on moderately small systems.  And using some form of recursion for parsing user input is very common...)

Exactly!

And conversion between binary and decimal is a good example. You know how many bits are in your int, so you know how many decimal digits deep the maximum recursion can be. The alternative is to generate the digits in the wrong order and use a temporary array to store them, and then use an extra loop to print them in the correct order afterwards. Between the array and the code for the extra loop the recursive version is simpler and cleaner and the memory use is little different.

[brucehoult]

Moreover, if you're going to do pointer arithmetic, as you do two lines above, sprinkle a few sizeof()s around or your code will crash and burn hard on the first machine it hits that doesn't agree with your assumptions on word size (which in this case appears to be (sizeof(int) == 1)). Better still, don't do pointer arithmetic unless it is absolutely forced on you, I know of nothing that creates fragile code faster than using pointer arithmetic. This doesn't mean you can't pass pointers around, just use '&' and '[]' to safely do all the address manipulation on your behalf.

A lot of people seem not to be aware or the properties of C arrays and pointers.

If you have...

T arr[sz];
int i;

... then all the following mean *exactly* the same thing in C:

arr  ==  *(arr+i)  ==  *(i+arr)  ==  i[arr]

That last one is probably a shock to most people reading, but it's perfectly true.

And therefore, taking the address:

&arr  ==  &*(arr+i)  == arr+i  == i+arr  ==  &*(i+arr)  ==  &i[arr]

Doing &arr is no more and no less safe than arr+i no matter what the type T is.

The only time you have to or should muck about with sizeof() is if you've converted the T* to a char* for some reason (or no good reason).

[sasa]

A lot of people seem not to be aware or the properties of C arrays and pointers.
If you have...

I'm starting to have a headache here - from advanced algorithms and recursion you are back to explain elementary C stuff...  There is no point - if somebody do not like or do not understand the code, it is not obligated to use it.

The main point is that almost any solved non trivial problem can be solved in several different ways and in minimum and maximum predicted time/steps. If time is relatively small according to other tasks, it can be used algorithm which allow optimal solution.

[T3sl4co1l]

And conversion between binary and decimal is a good example. You know how many bits are in your int, so you know how many decimal digits deep the maximum recursion can be. The alternative is to generate the digits in the wrong order and use a temporary array to store them, and then use an extra loop to print them in the correct order afterwards. Between the array and the code for the extra loop the recursive version is simpler and cleaner and the memory use is little different.

If you're in assembler, you can even push/pop that "array" yourself (probably not needing any other stacks for storing registers during the loop).  Otherwise, the only sure way* to make the compiler emit push and pop is: call a function!

*Hmm, aside from asm() and compiler internals, is there anything else known to cause this?  Perhaps reserving a register for multiple variables somehow?  Certainly nothing target-independent?

Tim

[Cerebus]

For a start, it violates my rule that you shouldn't have to know, with certainty, the operator precedences to be able to understand what a line of code does. If you're going to write a line of code like that, at least throw some brackets in so that: 1) a human will understand it, 2) the compiler will do what you intend if you've mis-remembered an operator precedence.

I'd say something is pretty wrong with your understanding of C if you don't know that ?: is lower precedence than everything except assignment operators.

Oh, I know the precedence. You completely miss the point. It's about error-proneness and human readability. I think the point is quite clearly made above

C is the simplest language out there. Learn it!

I probably learned C before you were born, and certainly with enough background to know that it is not "the simplest language out there", for example LOGO and smalltalk-80 are much, much simpler. In 1985 or 1986 I wrote (in C as it happens) a trivial* smalltalk-80 compiler (that spat out smalltalk-80 bytecode) literally in a day; I imagine that I'd probably have still been working 3 months later if I'd set out to write any kind of C compiler instead.

I don't think there's much point in addressing the rest of your comments point by point. The fact that a handful of people recognised the problem from:

  int *branch = right >= end | *left > *right ? left:right;

 sigh....

would suggest to a humble man that there might be a well recognised problem here and something to learn. The fact that you, quite clearly, want to argue about it suggests that trying to get you to mend your ways is a pointless exercise. Code being nominally correct is not a complete and sufficient condition for it being good code, indeed nominally correct code can still be bad code. A nominally correctly assembled big-box flat pack table might well work, but will it still be around and functioning after 400 years of use and maintenance like a carpenter's well crafted table will? Home Depot or Chippendale**? It's your choice, but I know which I'd rather be.

*Trivial in the sense that it could only compile a single method at a time. It was part of a (later abandoned) effort to bootstrap a smalltalk-80 system from the PARC books.

**Feel free to substitute Charles Rennie Mackintosh or any other well known furniture maker to your personal taste. Personally I can't stand Chippendale but his is probably the best known name in furniture and hence a useful touchstone example.

[brucehoult]

I probably learned C before you were born

ahahahaha.

I was born well before BCPL was developed, let alone B or C.

example LOGO and smalltalk-80 are much, much simpler. In 1985 or 1986 I wrote (in C as it happens) a trivial* smalltalk-80 compiler (that spat out smalltalk-80 bytecode) literally in a day

LOGO and smalltalk are simple languages to use, but complex in the implementation. Converting smalltalk to bytecode is a trivial operation (as it is for Java too) -- all the complexity is in the interpreter.

I was programming in all three of the languages you mention well before 1985. In 1985 and 1986 I was employed full time programming in PL/I (and PostScript, which earned me considerable consulting income over the next 10 or 15 years) and wishing the machine in question supported C, which I'd already been using for a few years -- or better "C with Classes" but I wasn't able to get my hands on an implementation of that until Zortech in 1988, and then a cfront in 1989.

You appear to believe that because someone disagrees with you they are young and inexperienced.
What was that about "a humble man"?

[Cerebus]

You appear to believe that because someone disagrees with you they are young and inexperienced.
What was that about "a humble man"?

"Young and inexperienced" is a more charitable interpretation, in the absence of knowing your age, than would be "Is old enough that he ought to know better".

You've clearly been around as long as I have. How can you not have learned what I'm talking about? Surely you've seen enough disaster ridden code to recognise that style as dangerous?

[bd139]

Indeed. I wrote a C compiler when I was young. Universe ending paradox!

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

[legacy]

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

I agree!

[X]

While debugging some customer code in production last week that kept crashing, I came across a recursive function. While it wasn't the recursiveness in itself that caused the problem on its own, it exacerbated the problem (memory allocated but not released).

I could see why the programmer chose to use recursion, but to me it seemed like they'd used it "because you can" rather than for readability reasons. Had the programmer remembered to release all his initialised variables as they dropped out of scope I might have given him more credence. Those initialised heap variables were arrays of strings that never changed  so should've been constants anyway, and never used either heap or stack. (The heap grew to... wait for it... 50GB before the process broke.)

I think that in over 30 years I can count on the digits of one hand the number of times I've come across recursion used outside the classroom, and this was one of them. Most of those times have been when looking at the C runtime library, such as qsort.

I've used recursion a few times in ordinary C code (not embedded) only in situations where I can control the depth of the recursion to reasonable limits (eg. searching through a very small tree that I know will be very small). It often makes for a nice solution that is simple to implement, if you can control the depth and keep stack usage in check.

If a non-recursive solution proves to be only slightly more painful than a recursive solution (eg. DFS), I will endure the pain as the end-result will not require me to control the inputs as strictly, and will not use up a lot of stack space.

One trap people fall into is not cleaning up before exiting the function thinking "the OS will do it anyway!" or "memory is cheap let's waste it bro!" As the 50GB heap usage in your example demonstrates, this is highly necessary. Once a process of mine crashed having exceeded the allowable per-process limit set by the OS (1GB I think) because I forgot to free() in one small function that is called thousands of times.

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

The biggest problem with C is the standards committee. They have enough rules to compare with the entire Australian federal tax legislation, and many of these C rules are vague enough as to require a Master's Degree to understand them. Many features (eg. variable length arrays in C11) are stupidly made optional. Many of the rules are "implementation-defined" and seem to defeat the purpose of having a standard in the first place. It is not a surprise some compilers can't implement all the features of C.

The second biggest problem is working on code that was written by developers who think C hasn't improved from the 1980s or refuse to use certain features (eg. postponed declarations, inline functions, stdint.h/stdbool.h etc) that would significantly improve the code just because Microsoft didn't support them until recently.

[Cerebus]

Indeed. I wrote a C compiler when I was young. Universe ending paradox!

Incidentally, C is a horrible horrible language full of non determinism and stupidity ergo you can never be experienced enough not to be hurt by it occasionally.

Can't argue with that, even though I probably write more C than everything else put together. I deeply mourn the loss, for all practical purposes, of Algol 68. Brian Kernighan said that some of the features of C were influenced by Algol 68, so why, oh why, did ":=" get abandoned in favour of "=" for assignment? The one C 'feature' that has bitten me more times than any other is accidentally typing something like

Code: [Select]

if (fred = bert) ...when I meant to type

Code: [Select]

if (fred == bert) ....

[aside] I was highly tempted, just for the obvious in joke, to create a second account under the name "bd140" and post the single and only message "I disagree with everything you've said, I think the exact opposite" as a comment to your message. For some reason, this idea hadn't occurred to me before today. Still, if I ever really disagree with you vehemently I can just threaten to walk over to my parts box and reach for the high voltage power supply.

[NorthGuy]

Back to the recursion.

There seems to be an opinion that there's a great value in tail recursion because it can be optimized by the compiler. And the other cases of recursion are "dangereous" and should be avoided.

I have opposite opinion. Tail recursion is a rudimentary form of recursion - mostly syntax than substance, and it relies on compiler optimization, which is undocumented feature that shouldn't be relied upon. Aside of that, recursion is very useful.

Really, if you're walking a linked list, why is the recursive walking:

Code: [Select]

void process_node(node_t *node) {
   if (node == NULL) return;
   do_something(node);
   process_node(node->next); // assuming compiler will optimize the tail call
}
is superior to a simple loop:

Code: [Select]

node_t *node = something;
while (node != NULL) {
   do_something(node);
   node = node->next;
}
?

There's really no difference, and there's no benefit of recursion because the recursive process doesn't use any memory and therefore can be easily re-written as a loop,

But recursion becomes really useful, not to mention very efficient, if there's a need to store something at every node. Why? Because it uses the stack memory as a storage. Without recursion, this memory would have to be somehow allocated/reserved.

For example, walking a tree (especially when you need to process children/siblings before the current node):

Code: [Select]

void process_node(node_t *node) {
   if (node == NULL) return;
   process_node(node->child); // process children
   process_node(node->next); // process siblings
   do_something(node); // process this node
}
Try to re-write this as a loop and you will see how useful the recursion is.

[bd139]

The second biggest problem is working on code that was written by developers who think C hasn't improved from the 1980s or refuse to use certain features (eg. postponed declarations, inline functions, stdint.h/stdbool.h etc) that would significantly improve the code just because Microsoft didn't support them until recently.

Those humans are what we refer to in the office as, and excuse the language, cunts. In context "Holy crap someone wrote DoSomethingEx(PARAM1_DEFAULT, PARAM2_DEFAULT, PARAM3_DEFAULT, &somethingAnnoying); ... cunt!"

Can't argue with that, even though I probably write more C than everything else put together. I deeply mourn the loss, for all practical purposes, of Algol 68. Brian Kernighan said that some of the features of C were influenced by Algol 68, so why, oh why, did ":=" get abandoned in favour of "=" for assignment? The one C 'feature' that has bitten me more times than any other is accidentally typing something like

Code: [Select]

if (fred = bert) ...when I meant to type

Code: [Select]

if (fred == bert) ....

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.

[aside] I was highly tempted, just for the obvious in joke, to create a second account under the name "bd140" and post the single and only message "I disagree with everything you've said, I think the exact opposite" as a comment to your message. For some reason, this idea hadn't occurred to me before today. Still, if I ever really disagree with you vehemently I can just threaten to walk over to my parts box and reach for the high voltage power supply.

If you were a BD140 I would have thought you'd be complementary 

[Sal Ammoniac]

Oh, I know the precedence. You completely miss the point. It's about error-proneness and human readability. I think the point is quite clearly made above

That particular line of code would not have made it past any code review I've ever been involved in. Our coding standards favor clear, easily understandable code over clever and/or complex code that tempts the precedence Gods.

[sasa]

That particular line of code would not have made it past any code review I've ever been involved in...

One notable benefit of the compact way of coding is to force compiler to make much more optimized code than usually. Otherwise, indeed they are mysterious ways how compiler will actually perform optimization. That could be crucial in speed critical parts of code, however most of the code should have to be clear, if used in large company with many employers.

[janoc]

If you have small enough N, it is enough even Bubble...

The only time I ever needed to sort something was when displaying a list of filenames, and then Bubble sort was plenty fast enough.

Ehm, try that with a directory containing a few thousands files. 

You may come to appreciate some other sorts than bubble sorts, which is pretty much the worst one in existence (most have a quadratic worst case, bubble sort is quadratic even in the average case).

[Mr. Scram]

I've used recursion for an Euclidean type algorithm without any trouble. I made sure to test how far I could take it before the program would throw a fit, and that was well beyond the realm of what it would ever be used for.

[janoc]

I have opposite opinion. Tail recursion is a rudimentary form of recursion - mostly syntax than substance, and it relies on compiler optimization, which is undocumented feature that shouldn't be relied upon. Aside of that, recursion is very useful.

Would disagree with that but then we would have to go into the theory of computability and formal reasoning about programs. In short, tail recursion allows to simplify reasoning about what the code does because such code is trivially mapped to mathematical induction. If you have arbitrary recursion, this doesn't work and you need to first massage the code to convert it to tail form (which isn't always possible).

Also the tail call optimization is certainly documented if the compiler/language supports it (both LLVM/CLANG and GCC do, for ex.). For GCC this has been around since 2002 or so, just don't forget to turn on -O2 optimization level (or higher).

Tail calls permit to eliminate the entire stack frame because the compiler knows that the variables stored there will not be used anymore (since the only thing following the tail call is return). This eliminates problems with overflowing stacks, for example. It is certainly not only syntactic sugar! Non-tail recursion cannot be optimized like this and you will blow out of RAM sooner or later, given sufficient amount of data. It is very rare that a recursive algorithm cannot be expressed in tail form, so I would say that a lot of people complaining about recursion don't use it properly.

And to add something to your comparison with iteration - another advantage of recursion is that there many many algorithms which can be naturally expressed as:

• Do something with the first/one/first few element(s)
• Apply this function to the rest

Processing lists, trees, graphs, sorting, merging, various filters, etc. - all of these things can be (and commonly are) naturally expressed in this way. If there is some recurrent math formula behind then recursion is a great tool, leading to natural implementation. Just make sure it finishes - there is a good rule of thumb for that: Something needs to decrease with every step.

[NorthGuy]

And to add something to your comparison with iteration - another advantage of recursion is that there many many algorithms which can be naturally expressed as:

• Do something with the first/one/first few element(s)
• Apply this function to the rest

Translating what you have into "machine" language, I would naturally do something like:

Code: [Select]

do_something(x[0]); // Do something with the first/one/first few element(s)
for (i = 1; i < n; i++) {
  do_something(x[i]); // Apply this function to the rest
}
or simply

Code: [Select]

for (i = 0; i < n; i++) {
  do_something(x[i]);
}
I don't see how recursion is "natural" here.

There's no reason to use recursion where it is not needed (e.g. where you necessarily want to use tail recursion because you feel it's cool). Similarly, there's no reason not to use recursion where the recursion helps (e.g. no reason to avoid recursion because you're scared of how dangerous it is). This is just as with everything else - forget the rules and use your brain cells instead.

[bd139]

Just to reply to a comment about tail recursion, this isn't represented in the machine as a recursion operation but a continuation via tail call optimisation which is a thoroughly different concept. It suits recursive algorithms nicely where the final call is the calling function. At that point you don't need to create a new stack frame and futz the stack. That's perfectly deterministic to optimise out. Hell if you have a test case you can even make sure it doesn't shit the stack. LLVM at least has a half decent optimiser that can actually handle this well  (unlike GCC which is a hairy testicle).

You C guys really need to go on a mental excursion and write some Haskell, Scheme or Erlang or something and come back having licked the toad of glory even if you never touch it again.

Also to note, the stack and stack frames are a compromise in the machine model which happens to leak into the language abstraction, not a required part of the machine or the language. There doesn't have to be turtles all the way down until they topple with a stack overflow; there can be one well defined turtle. Some embedded systems guys may recognise this if they have dirty assembly fingers. There was another thread on that where all the C programmers whinged about goto (or JMP as it used to be called)

[sasa]

If there is some recurrent math formula behind then recursion is a great tool, leading to natural implementation.

That is exactly where fresh university graduated youngsters may break they tooths when start to bite that simple challenge...

They may use blindly as an axiom that if recurrent math formula is defined in such matter, it is "natural" to do that in code. Certainly, that is not the general rule at all.

Take for instance continued fractions. Dealing with finite and infinite expression makes fundamental difference in approach for implementation - no recursion is necessary. Not a single computational process is infinite if approximate or accurate result is expected in reasonable time.

[Bruce Abbott]

But recursion becomes really useful, not to mention very efficient, if there's a need to store something at every node. Why? Because it uses the stack memory as a storage. Without recursion, this memory would have to be somehow allocated/reserved.

Stack is not allocated/reserved?

Using stack may be a more efficient use of memory if you have enough of it, but what if you don't? And how do you know that you have enough? Oh right - you just give your task plenty of stack, to (hopefully) ensure that it won't run out. So now all that memory isn't available to anything that can't go on the stack. How is that efficient?

[NorthGuy]

Using stack may be a more efficient use of memory if you have enough of it, but what if you don't? And how do you know that you have enough? Oh right - you just give your task plenty of stack, to (hopefully) ensure that it won't run out. So now all that memory isn't available to anything that can't go on the stack. How is that efficient?

Stack is the most efficient storage. Getting memory from the stack very quick and there's no gaps (so memory is not wasted). the memory is automatically freed when the function quits and is subsequently re-used.

How do you know how much is enough? You estimate. It is not very hard.

Typically, in the embedded app, all the unallocated memory goes to stack - no other use for it. If you don't have enough stack, you must conserve memory somehow or get a bigger part. Moving the memory from the stack to static allocation or to heap (if you have one) won't solve the problem.