3 ms·

Funny side story is that Hoare couldn't publish algorithm for QuickSort until he learned ALGOL was ready to do recursion. QuickSort is one of the algorithms tha

by sytelus 11y ago

Funny side story is that Hoare couldn't publish algorithm for QuickSort until he learned ALGOL was ready to do recursion. QuickSort is one of the algorithms that is very difficult to do without having a concept of recursion. Another one is various tree traversals. What are the other algorithms that would be impractical without recursion? PS: Using stack to simulate recursion doesn't count :).

munificent 11y ago
> What are the other algorithms that would be impractical without recursion? Interestingly, writing a compiler. Since expressions nest, it's very hard to write a compiler for them without a recursive function for compiling an expression.
copperx 11y ago
The implementations of non-recursive Quicksort and tree traversal are not impractical, just a little bit longer. By the way, are recursive versions of sorting algorithms even shipped with standard libraries of popular languages?
- sytelus 11y ago
  Yes, Java as well as .Net implementations used recursive QuickSort (I think Java recently switched to Timsort?). The implementation however used only one recursive call instead of two as in textbooks because second call is tail recursive and can be made iterative. This is however not done just to avoid recursion. With QuickSort you run risk of using up O(n) stack space in worse case. Making second call iterative allows to make sure recursion always occur on smaller partition thus guerenteeing O(lg n) space.
- CJefferson 11y ago
  Certainly std::sort and friends are recursive in all C++ implementations I've looked at. In C++ it's hard to make the efficient and non-recursive. You can have a fixed-sized buffer (limits depth), or call malloc for a buffer (a single call to malloc can be more expensive than just doing the sort on the stack, and in general the C++ standard library tries hard to avoid mallocing).
jkot 11y ago
Most papers on BTrees I read are not using recursion.

by sytelus 11y ago

munificent 11y ago

> What are the other algorithms that would be impractical without recursion? Interestingly, writing a compiler. Since expressions nest, it's very hard to write a compiler for them without a recursive function for compiling an expression.

copperx 11y ago

The implementations of non-recursive Quicksort and tree traversal are not impractical, just a little bit longer. By the way, are recursive versions of sorting algorithms even shipped with standard libraries of popular languages?

sytelus 11y ago
Yes, Java as well as .Net implementations used recursive QuickSort (I think Java recently switched to Timsort?). The implementation however used only one recursive call instead of two as in textbooks because second call is tail recursive and can be made iterative. This is however not done just to avoid recursion. With QuickSort you run risk of using up O(n) stack space in worse case. Making second call iterative allows to make sure recursion always occur on smaller partition thus guerenteeing O(lg n) space.
CJefferson 11y ago
Certainly std::sort and friends are recursive in all C++ implementations I've looked at. In C++ it's hard to make the efficient and non-recursive. You can have a fixed-sized buffer (limits depth), or call malloc for a buffer (a single call to malloc can be more expensive than just doing the sort on the stack, and in general the C++ standard library tries hard to avoid mallocing).

jkot 11y ago

Most papers on BTrees I read are not using recursion.