Recursion - do you use it in the real world?

[hamster_nz]

Code: [Select]


int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

So I now compute factorial 300,000, and watch my program segfault....

Hmmmm. Let me try that...

Code: [Select]

$ gcc recfact.cpp -c -Os -o recfact.o
$ objdump -d recfact.o

recfact.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <_Z9factoriali>:
   0: 4785                li a5,1
   2: 873e                mv a4,a5

0000000000000004 <.L3>:
   4: 00e50663          beq a0,a4,10 <.L1>
   8: 02a787bb          mulw a5,a5,a0
   c: 357d                addiw a0,a0,-1
   e: bfdd                j 4 <.L3>

0000000000000010 <.L1>:
  10: 853e                mv a0,a5
  12: 8082                ret

Yeah, nah .. no segfault there, your stack will be fine.

*Arithmetic* overflow, however ,,, for sure.

(Sigh - nobody trusts anybody on the interweb any more)

Code: [Select]

$ cat factorial.c
#include <stdio.h>

int factorial(int i) {
   return (i == 1) ? 1 : i*factorial(i-1);
}

int main(int argc, char *argv[]) {
   int i;

   i = 4;
   printf("Factorial(%i) is %i \n", i, factorial(i));
   fflush(stdout);

   i = 300000;
   printf("Factorial(%i) is %i \n", i, factorial(i));
   fflush(stdout);
}
$ gcc -o factorial factorial.c -Wall -pedantic
$ ./factorial
Factorial(4) is 24
Segmentation fault (core dumped)
$

So a technique that gives fatal runtime errors if you level the optimizations turned off???  Nice!

Recursion? Yeah nah...

...and it doesn't matter about the overflow - it could just as well be any algorithm that can be expressed recursively. e.g. Daily interest. I was just using factorial() as it is the 'textbook' recursion example, and complex functions would bomb out sooner as they would have larger stack frames.

[brucehoult]

Take for example mentioned sorting. Everybody know that original QSort is one of the fastest in-place sorting algorithms (except in worst case scenarios), however his recursive nature may be extremely dangerous. If there is maximally 100's of data to sort, the most optimal solution may be to use Shell or even Insertion...

The danger with quicksort isn't it's recursive nature, but that it can degenerate to iteration!

If you do even the absolute minimal thing of checking the size of each half of the partition and recursing on the smaller one first then you limit the stack to at most O(log n), as the second call is a tail-call. That's at most 30 or so for any practical example. The worst case scenarios (in terms of time) are then the ones that use the *least* stack.

Quicksort's worst case time is the same as Insertion sort's best case, so it's fairly pointless recommending insertion sort as a better replacement :-)

Shell sort has short and simple code, which may be useful in some cases, but it's critically dependent on the distance sequence used. Shell's original sequence has a worst case of O(N^2) (no better than insertion sort or degenerate quicksort), but several other simple sequences can give O(N^(4/3)) (five times worse than quicksort or heapsort or mergesort for a million elements) or O(N * log^2 N) (twenty times worse than quicksort or heapsort or mergesort for a million elements).

Heapsort is the best general purpose sort if you're worried about worst case. It's twice slower than quicksort on average, but always O(N * log N) and needs only about fifteen lines of code:

Code: [Select]

void siftDown(int *v, int *end, int *p){
  int *left = v + 2*(p-v) + 1, *right = left+1;
  if (left >= end) return;
  int *branch = right >= end | *left > *right ? left:right;
  if (*p >= *branch) return;
  swap(branch, p);
  siftDown(v, end, branch);
}

void heapSort(int *v, int *end){
  for (int *i = v+(end-v-1)/2; i>=v; --i) siftDown(v, end, i);
  while (--end > v){
    swap(v, end);
    siftDown(v, end, v);
  }
}


[brucehoult]

So a technique that gives fatal runtime errors if you level the optimizations turned off???  Nice!

Why on earth would you turn the best half of the compiler off? You might as well program in assembly language then. The compiler is your friend. With modern ones, optimisation doesn't even hurt the debugger.

[hans]

If you're doing any kind of real-time systems I certainly hope you're not surrending to compiler optimisations to make code predictable in it's execution time. Giving some meaningful statements about worst case timing will become hard, so better avoid recursion at all costs.
And yes, you want the program to work without optimisations. Try debugging your code with -O1, half of the breakpoints and locals will be unresolvable.

Stack usage is also a common reason to avoid recursion.

I think recursion can be useful in meta programming, which is more a thing in C++ than in just plain C. Especially if you use recursion in some kind of constants derivation, it can be OK if you can trick the compiler to evaluate as much as possible during compilation time (e.g. use constexpr effectively). The problem is that also these kind of tricks have their limits, e.g. GCC has it's max recursion depth set to 512 as default.

In college we have been demonstrated how to use recursoin also in languages like VHDL. You certainly don't want to do data dependent recursion there, as each recursion depth will generate new hardware. However recursion depending on data structures is possible, but often it's easier and more clear to write the iterative variant.

[hamster_nz]

So a technique that gives fatal runtime errors if you level the optimizations turned off???  Nice!

Why on earth would you turn the best half of the compiler off? You might as well program in assembly language then. The compiler is your friend. With modern ones, optimisation doesn't even hurt the debugger.

It is simple - because I can.

One of the basic tenets of optimizing compilers is that the program should give the same output for the same input, the only thing is that it should be different is the performance or code size, or whatever metric you are optimizing for.

When developing code, I turn optimizations all the way up - I get far better reporting of errors, warning and any crappy code (like uninitialzed variables). It gives me more insight (and faster code, of course)

When debugging particularly hard bugs I quite often turn optimizations down for the module concerned, and check the bug is still there. Usually it is still there, so I can debug it with the state of the system always matching the state that is implied by the code.

[T3sl4co1l]

If you're doing any kind of real-time systems I certainly hope you're not surrending to compiler optimisations to make code predictable in it's execution time. Giving some meaningful statements about worst case timing will become hard, so better avoid recursion at all costs.
And yes, you want the program to work without optimisations. Try debugging your code with -O1, half of the breakpoints and locals will be unresolvable.

And, of course, anywhere the run time is critical, learn your target machines's instruction set, and inspect the compiler's assembler output!  This is also a useful pre-debugging step when the code the compiler is generating doesn't seem to make sense.

Stack usage is also a common reason to avoid recursion.

I think recursion can be useful in meta programming, which is more a thing in C++ than in just plain C. Especially if you use recursion in some kind of constants derivation, it can be OK if you can trick the compiler to evaluate as much as possible during compilation time (e.g. use constexpr effectively). The problem is that also these kind of tricks have their limits, e.g. GCC has it's max recursion depth set to 512 as default.

The downside may be the generation of a crapload of executable code, much like the VHDL case with hardware.  This can be helpful on machines with GB of RAM (cellphones maybe, PCs usually), but watch carefully for bloat on embedded systems.

An extreme example might be integrating a JIT compiler with your application, say to solve a particular instance of a combinatorially prohibitive execution tree.  A realization of this: Abrash's UT2k3 software render pipeline (search to find the series of articles).

For 99.9999% of all programs, such extremes are neither necessary nor desirable (JS does this constantly, I guess, and look at how much overhead is spent on that!) -- again, it's just another tool to be aware of; another way of thinking about programming that can inspire you in simpler cases.

Tim

[sasa]

The danger with quicksort isn't it's recursive nature, but that it can degenerate to iteration!
..

I'm not sure I following you... If any of conditions is not satisfied, new recursion call is executed and thus risk for resource. In any worst case scenario, we will have N nested recursion calls.

In the past I have modified original QSort algorithm in such manners that have no single worst-case scenario. Without much lose in speed in random data distribution (few percents only, regardless N) and as a benefit, if there is small number of different elements it is much faster (speed is comparable to Radix)... I honestly wonder how Hoare misses that...

Heap is not in-place sorting algorithm and if you are limited with memory, it is pointless. And as any binary tree, worst case scenario is known.

If you have small enough N, it is enough even Bubble...  The best solution is hybrid algorithm, which will use suitable algorithm regarding N, type of data and available resources.

As mentioned, all depends on exact requirements.

[Bruce Abbott]

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. 

[brucehoult]

The danger with quicksort isn't it's recursive nature, but that it can degenerate to iteration!
..

I'm not sure I following you... If any of conditions is not satisfied, new recursion call is executed and thus risk for resource. In any worst case scenario, we will have N*N recursions.

That's not correct.

The worst case for quicksort is when a partitioning step chooses the minimum or maximum element as the "pivot" and therefore ends up with partitions [0 elements; the pivot; N-1 elements]

You make a recursive call on the 0 element partition, which will be rather quick and use next to no stack. Then you make a tail-recursive call to sort the N-1 element partition. This reuses the same stack frame as you are already in and therefore uses no memory resources.

Heap is not in-place sorting algorithm and if you are limited with memory, it is pointless. And as any binary tree, worst case scenario is known.

Certainly heap sort is an in-place sorting algorithm! Read the code I posted here a few hours ago.

[NorthGuy]

The worst case for quicksort is when a partitioning step chooses the minimum or maximum element as the "pivot" and therefore ends up with partitions [0 elements; the pivot; N-1 elements]

It also might be [N-1 elements; the pivot; 0 elements] on every iteration, in which case your tail call will be wasted on the 0-element case, so you will get N levels of recursion - N*16 stack size on a 32-bit machine.

[helius]

It also might be [N-1 elements; the pivot; 0 elements] on every iteration, in which case your tail call will be wasted on the 0-element case, so you will get N levels of recursion - N*16 stack size on a 32-bit machine.

So conditionally swap L and U before making the two recursive calls. Isn't that obvious?

Your respondent already wrote

If you do even the absolute minimal thing of checking the size of each half of the partition and recursing on the smaller one first then you limit the stack to at most O(log n), as the second call is a tail-call.

(emphasis added)

[NorthGuy]

So conditionally swap L and U before making the two recursive calls. Isn't that obvious?

IMHO, it is easier to achieve the same effect by avoiding the tail recursion call altogether. Not to mention it wouldn't rely on complier optimisation.

The original:

Code: [Select]

void sort(int a, int b) {
   ...
   sort(a,j);
   sort(i,b);
}
You suggest:

Code: [Select]

void sort(int a, int b) {
   ...
   if ((j - a) > (b - i)) {
     a1 = i;
     b1 = b;
     a2 = a;
     b2 = j;
   } else {
     a1 = a;
     b1 = j;
     a2 = i;
     b2 = b;
   }
   sort(a1,b1);
   sort(a2,b2);
}
Without tail recursion:

Code: [Select]

void sort(int a, int b) {
  while (1) {
     ...
     if ((j - a) > (b - i)) {
       sort(i,b);
       b = j;
     } else {
       sort(a,j);
       a = i;
     }
  }
}

[Feynman]

I never use recursion. I'm developing embedded C and every decent coding standard forbids recursion for good reason

[brucehoult]

So conditionally swap L and U before making the two recursive calls. Isn't that obvious?

IMHO, it is easier to achieve the same effect by avoiding the tail recursion call altogether. Not to mention it wouldn't rely on complier optimisation.

As you say, a tail call is exactly equivalent to a loop. But it's easier to understand. Why not rely on the compiler to convert it instead of you? Unless you're writing your own compiler, the people at gcc or llvm implemented this optimisation many years ago -- and got it correct.

Code: [Select]

void sort(int a, int b) {
  while (1) {
     ...
     if ((j - a) > (b - i)) {
       sort(i,b);
       b = j;
     } else {
       sort(a,j);
       a = i;
     }
  }
}

Congratulations on your infinite loop :-)

Try "while (a < b)".

Or, better, use "while ((b - a) > 10)" and leave the array not quite sorted, and follow the quicksort up with an insertion sort on the whole array. That's even faster, overall. (of course that's an "if" not a "while" in the recursive formulation)

[brucehoult]

I never use recursion. I'm developing embedded C and every decent coding standard forbids recursion for good reason

No. For bad, superstitious reasons.

If you understand your algorithm and there are maximum bounds on the depth of recursion then it's absolutely fine to use it. If there aren't bounds on the depth of recursion then rewriting it as an iteration isn't going to help you. If you don't know the bounds then you shouldn't be let loose near an embedded system.

[bd139]

Indeed. You can blow the stack simply with deep abstractions. Look at the shit the java dudes throw out. I got a 2500 line stack once with no recursion!

[EntropyWizard]

It's a bit subtle, but you should google recursion.

[Cerebus]

It's a bit subtle, but you should google recursion.

As the third person to make a recursive recursion joke in this thread you win the grand prize - a free trip to a Siberian re-education camp.

[Sal Ammoniac]

My answer to this question would have to be in two parts:

On PCs and other general purpose computers: Yes, I use it whenever it makes sense.

On embedded systems: Never.

[NorthGuy]

Code: [Select]

void sort(int a, int b) {
  while (1) {
     ...
     if ((j - a) > (b - i)) {
       sort(i,b);
       b = j;
     } else {
       sort(a,j);
       a = i;
     }
  }
}

Congratulations on your infinite loop :-)

Try "while (a < b)".

Or, better, use "while ((b - a) > 10)" and leave the array not quite sorted, and follow the quicksort up with an insertion sort on the whole array. That's even faster, overall. (of course that's an "if" not a "while" in the recursive formulation)

It's not quite infinite. The "..." part represents quicksort actually sorting things. It'll return when it's nothing more to sort.

[ehughes]

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

 sigh....

[Sal Ammoniac]

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

 sigh....

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

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

[Cerebus]

  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.

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.

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.

[NorthGuy]

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.

Since both operands are either 0 or 1, "|" will produce the same result as "||".

The distinction is that "||" creates a sequencing point, and if the operand on the left is "true", then the complier must not evaluate the operand on the right. With "|", the order of evaluation is not defined (determined by the compiler) and the compiler may decide to evaluate the operand on the right first. Should this happen, evaluation of "*right" may cause a crash.