6 ms·

How often is recursion used in everyday, imperative-style code? Do stack limits make it impractical to use?

skrebbel 12y ago
Commonly when traversing hierarchical data structures. If you're certain the data structure isn't accidentally cyclic or extremely deep, there should be no problems.
- supahfly_remix 12y ago
  How does the code handle a stack overflow? Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. Can you point me to some code?
  - ars 12y ago
    Try it, just write a tiny function that calls itself and has a local variable (make sure to use the variable after the function call so it's not optimized away). Something like: int recurse(int foo) { int bar; printf("%d\n", foo); bar = recurse(foo + 1); printf("%d\n", bar); //this is just to avoid bar being optimized away return bar; } By me it seg-faults after 174,594 calls. Presumably that has to do with the size of the stack and the memory allocated for the function.
    - supahfly_remix 12y ago
      Thanks -- I just tried it, it came out to over 200k calls for me. It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this?
      - ars 12y ago
        > you have to anticipate and handle a stack overflow cleanly. How do you do this? You use sigaltstack and catch SIGSEGV. It's probably easier to handle if you hit a soft limit rather than the heap. Then you raise the limit, set a flag to make your functions unwind and reduce the limit again.
      - danbruc 12y ago
        You just don't write a recursive program if there is the possibility that it may run out of stack space due to the provided arguments.
      - Gmo 12y ago
        This is implementation dependent. In the JVM and the .NET VM, you can't handle it cleanly.
      - Chris_Newton 12y ago
        It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this? In principle, you have that problem with almost any language that uses the system stack to pass arguments when it makes a function call. It just happens to be easier to trigger it if you use a recursive algorithm, because it’s unlikely that you would write a program with 200,000 distinct functions each of which just called the next in a chain until something fell over. In practice, recursive algorithms are often used to walk recursive data structures and often have logarithmic complexity in the size of the data structure. Even structures that fill the memory of a supercomputer probably aren’t going to need more than a few hundred levels of recursion in that scenario, while the available stack space is probably several orders of magnitude larger. So to be blunt, unless you really are talking about something where failure really isn’t an option (safety critical systems and the like), you probably just treat this as the same kind of catastrophic failure that running out of system memory would be, and use some OS-level support to abort as gracefully as you can if the sky falls. If you really are working in a more constrained environment — safety-critical code, say, or perhaps an embedded system with relatively little memory — then it might be the case that you simply avoid the recursion altogether unless you’re using a language that guarantees tail recursion will be dealt with robustly. Some coding standards forbid the use of dynamically allocated memory for much the same reason, and you just have to use different tools to solve those problems if you’re working with such constraints.
  - skybrian 12y ago
    It's typically handled by ignoring the issue and bumping up the maximum stack size if it becomes a problem. For example, I once wrote a Java indexer that simply failed on very long chains of function calls. A better fix is to add a work queue or stack.
  - bnegreve 12y ago
    > Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. On Linux (and probably on other OSs) it's not easy to detect that the system is out heap memory because of lazy memory allocation policies. Physical memory is not allocated when you call malloc() but when you first read or write the corresponding memory page. Because of this, malloc() does not necessarily return NULL even if there isn't enough memory available on the system at the time you called malloc(). But if the system is still out of memory when your first access the allocated memory, your program will crash with a segfault. So in absence of extra precaution, using heap memory isn't any safer than using stack memory.
jimktrains2 12y ago
Stack limits are pretty large. It's a natural way to express many problems such as graphs (and their subsets trees). When people talk of "Tail Call Optimization" (TCO) they are talking about a way to recurse without leaving things on the stack (tail-call meaning that the recuse call is the last thing in the function so the state of the function doesn't need pushed on the stack, it can be discarded.
- supahfly_remix 12y ago
  Oh, I definitely see the elegance of expression programs or concepts recursively. Is TCO used in C++? I've only ever seen it mentioned in reference to Scheme and Haskell. It's a compiler optimization, so it would be transparent to the programmer, right?
  - supergauntlet 12y ago
    C++ optimizes only with -O2 or /O2 passed to the compiler (for GCC and MSVC++, not sure about Clang).
    - pflanze 12y ago
      You can't count on it in the general case even with gcc (even when taking care to heed the restrictions like not passing pointers to data on the stack, and putting all functions into the same compilation unit). I did tests a couple years ago where it would compile up to about a handful of mutually recursive functions with TCO, then when you added one more, it would disable TCO. I guess because some algorithm will stop analyzing the call graph past a certain mark and then disallow TCO from being applied.
    - pjmlp 12y ago
      If it isn't on the standard, anything goes. There are much more compilers out there than those three.
  - actsasbuffoon 12y ago
    TCO is available in plenty of other languages as well. Scala, Clojure, Erlang, and Elixir support it out of the box. Ruby has a VM setting for it, and there was a proposal to add it to JavaScript. I'm sure there are plenty of others.
cheery 12y ago
It depends on what you call 'everyday imperative-style code'. Without defining that, every answer to your question is correct.
skriticos2 12y ago
Admittedly recursion is not done often, but in some cases it's very useful. For example, recently I created an application with a tree record structure where the user could delete a node and it needed to delete all sub-nodes. With recursion it's easy to tell: 'call yourself for all subnodes you have, then delete yourself'. This is something that's much more difficult to express with the usual for/while constructs. Example: https://github.com/skriticos/tac_workflow/blob/9890e66d60851bd36af244294d94e1418e7b410d/workflow.py#L45-L49 https://github.com/skriticos/tac_workflow/blob/9890e66d60851...
al2o3cr 12y ago
Recursion can be a good fit for anything that's using a naturally-recursive process: for instance, when processing files in a directory along with all the files in subdirectories. Stack limits may or may not be a concern, depending on the application. In the case of directories, if you've got them nested 10k+ deep you've got other problems.
axman6 12y ago
I've written some nice, very clear C code using recursion; a nice example was a simple copying garbage collector which has something like 2-3 words of overhead on the stack per recursive call (made use of some global variables to reduce the number of arguments passed between functions though). The actual moving code was only maybe 10 lines.

Commonly when traversing hierarchical data structures. If you're certain the data structure isn't accidentally cyclic or extremely deep, there should be no problems.

supahfly_remix 12y ago
How does the code handle a stack overflow? Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. Can you point me to some code?
- ars 12y ago
  Try it, just write a tiny function that calls itself and has a local variable (make sure to use the variable after the function call so it's not optimized away). Something like: int recurse(int foo) { int bar; printf("%d\n", foo); bar = recurse(foo + 1); printf("%d\n", bar); //this is just to avoid bar being optimized away return bar; } By me it seg-faults after 174,594 calls. Presumably that has to do with the size of the stack and the memory allocated for the function.
  - supahfly_remix 12y ago
    Thanks -- I just tried it, it came out to over 200k calls for me. It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this?
    - ars 12y ago
      > you have to anticipate and handle a stack overflow cleanly. How do you do this? You use sigaltstack and catch SIGSEGV. It's probably easier to handle if you hit a soft limit rather than the heap. Then you raise the limit, set a flag to make your functions unwind and reduce the limit again.
    - danbruc 12y ago
      You just don't write a recursive program if there is the possibility that it may run out of stack space due to the provided arguments.
    - Gmo 12y ago
      This is implementation dependent. In the JVM and the .NET VM, you can't handle it cleanly.
    - Chris_Newton 12y ago
      It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this? In principle, you have that problem with almost any language that uses the system stack to pass arguments when it makes a function call. It just happens to be easier to trigger it if you use a recursive algorithm, because it’s unlikely that you would write a program with 200,000 distinct functions each of which just called the next in a chain until something fell over. In practice, recursive algorithms are often used to walk recursive data structures and often have logarithmic complexity in the size of the data structure. Even structures that fill the memory of a supercomputer probably aren’t going to need more than a few hundred levels of recursion in that scenario, while the available stack space is probably several orders of magnitude larger. So to be blunt, unless you really are talking about something where failure really isn’t an option (safety critical systems and the like), you probably just treat this as the same kind of catastrophic failure that running out of system memory would be, and use some OS-level support to abort as gracefully as you can if the sky falls. If you really are working in a more constrained environment — safety-critical code, say, or perhaps an embedded system with relatively little memory — then it might be the case that you simply avoid the recursion altogether unless you’re using a language that guarantees tail recursion will be dealt with robustly. Some coding standards forbid the use of dynamically allocated memory for much the same reason, and you just have to use different tools to solve those problems if you’re working with such constraints.
- skybrian 12y ago
  It's typically handled by ignoring the issue and bumping up the maximum stack size if it becomes a problem. For example, I once wrote a Java indexer that simply failed on very long chains of function calls. A better fix is to add a work queue or stack.
- bnegreve 12y ago
  > Stack overflows seems opaque to me, while preallocating memory (malloc) has mechanism to signal failures for proper handling. On Linux (and probably on other OSs) it's not easy to detect that the system is out heap memory because of lazy memory allocation policies. Physical memory is not allocated when you call malloc() but when you first read or write the corresponding memory page. Because of this, malloc() does not necessarily return NULL even if there isn't enough memory available on the system at the time you called malloc(). But if the system is still out of memory when your first access the allocated memory, your program will crash with a segfault. So in absence of extra precaution, using heap memory isn't any safer than using stack memory.

jimktrains2 12y ago

Stack limits are pretty large. It's a natural way to express many problems such as graphs (and their subsets trees). When people talk of "Tail Call Optimization" (TCO) they are talking about a way to recurse without leaving things on the stack (tail-call meaning that the recuse call is the last thing in the function so the state of the function doesn't need pushed on the stack, it can be discarded.

supahfly_remix 12y ago
Oh, I definitely see the elegance of expression programs or concepts recursively. Is TCO used in C++? I've only ever seen it mentioned in reference to Scheme and Haskell. It's a compiler optimization, so it would be transparent to the programmer, right?
- supergauntlet 12y ago
  C++ optimizes only with -O2 or /O2 passed to the compiler (for GCC and MSVC++, not sure about Clang).
  - pflanze 12y ago
    You can't count on it in the general case even with gcc (even when taking care to heed the restrictions like not passing pointers to data on the stack, and putting all functions into the same compilation unit). I did tests a couple years ago where it would compile up to about a handful of mutually recursive functions with TCO, then when you added one more, it would disable TCO. I guess because some algorithm will stop analyzing the call graph past a certain mark and then disallow TCO from being applied.
  - pjmlp 12y ago
    If it isn't on the standard, anything goes. There are much more compilers out there than those three.
- actsasbuffoon 12y ago
  TCO is available in plenty of other languages as well. Scala, Clojure, Erlang, and Elixir support it out of the box. Ruby has a VM setting for it, and there was a proposal to add it to JavaScript. I'm sure there are plenty of others.

cheery 12y ago

It depends on what you call 'everyday imperative-style code'. Without defining that, every answer to your question is correct.

skriticos2 12y ago

Admittedly recursion is not done often, but in some cases it's very useful. For example, recently I created an application with a tree record structure where the user could delete a node and it needed to delete all sub-nodes. With recursion it's easy to tell: 'call yourself for all subnodes you have, then delete yourself'. This is something that's much more difficult to express with the usual for/while constructs. Example: https://github.com/skriticos/tac_workflow/blob/9890e66d60851bd36af244294d94e1418e7b410d/workflow.py#L45-L49 https://github.com/skriticos/tac_workflow/blob/9890e66d60851...

al2o3cr 12y ago

Recursion can be a good fit for anything that's using a naturally-recursive process: for instance, when processing files in a directory along with all the files in subdirectories. Stack limits may or may not be a concern, depending on the application. In the case of directories, if you've got them nested 10k+ deep you've got other problems.

axman6 12y ago

I've written some nice, very clear C code using recursion; a nice example was a simple copying garbage collector which has something like 2-3 words of overhead on the stack per recursive call (made use of some global variables to reduce the number of arguments passed between functions though). The actual moving code was only maybe 10 lines.