7 ms·

Ah recursion, my old nemesis. We meet again. Very interesting and informative article, but I'm with the SUBSET people on this one: > Do not write recursive pro

by dvt 11y ago

Ah recursion, my old nemesis. We meet again. Very interesting and informative article, but I'm with the SUBSET people on this one: > Do not write recursive procedures. Do not use procedures recursively. I've probably failed 90% of recursion "gotcha'" questions I've had during interviews. It's my uninformed opinion that recursion is uninteresting and unintuitive. This is why whenever I encounter it, I either ignore it or refactor it. I'm exaggerating, of course, but I really do hate it. There are some very interesting theoretical applications, however. The article briefly mentions Lambda Calculus (which I love) where I've always enjoyed playing with the divergent Omega combinator[1]: Ω = (λx. x x) (λx. x x) I'm may be entirely too stupid to appreciate the beautiful intricacies of recursive programming, but I do think that recursive programming can be susceptible to some unique bugs, such as exceeding stack/heap, that are very difficult to notice prima facia (more difficult than when the same is done via procedural code, at least). [1] http://www.seas.upenn.edu/~cis500/cis500-f06/lectures/0925-2x3.pdf http://www.seas.upenn.edu/~cis500/cis500-f06/lectures/0925-2...

rblatz 11y ago
I'm fairly sure Dijkstra didn't say that, since he was advocating for recursion to be added. It was one of the splinter Algol groups that added that sentence trying to remove it.
- dvt 11y ago
  Whoops, I misunderstood, had to re-read that paragraph :)
  - rblatz 11y ago
    No worries, I reread it multiple times to make sure I had it right. Not the clearest paragraph.
baddox 11y ago
I find recursion extremely intuitive, if not necessary, for pretty much any data structure with a bunch of things ("nodes") pointing to other things. That includes, most notably, linked lists and trees. I can probably work up recursive pseudocode for tree traversals pretty easily, despite not having studied computer science or doing it at work for several years, yet I find an iterative solution somewhat elusive and unnatural.
- dvt 11y ago
  Different strokes for different folks, as they say.
  - baddox 11y ago
    I agree, but do you really think of a binary tree traversal iteratively? I won't say it's wrong, but I am extremely surprised.
    - erikpukinskis 11y ago
      It depends somewhat on what you are doing. If you are on a walk through a (metaphorical) forest, do you think of yourself on a subpath of a subpath of a subpath, or is it just "well I guess I'm here now!"? If you are just doing a simple search, maybe you don't need to keep that whole stack around. An iterative approach makes a lot of sense. If you are building a map of the tree and you're not even sure what scale to make it, you might want to reserve judgement about the supertree while you explore some sub trees so you might be glad that stack is there, and you might profit from thinking about that situation as recursion. But the answer is: yes, a lot of things you do with trees make a lot of sense as simple procedures.
    - dvt 11y ago
      No, I think about it recursively. But it hurts my brain. And to be fair, tree traversal is one of the things I find pretty intuitive about recursion. Other stuff, not so much. Consider the Fibonacci Sequence written recursively.
      - davexunit 11y ago
        The recursive definition is intuitive and easy to come up with given its mathematical definition. To avoid redundant computation, the function can be memoized. Yes, you can write it linearly as well, but oftentimes the linear algorithm is harder to come up with. SICP spends a lot of time on this subject in one of its early chapters and its worth a read. Also, some languages support recursion better than others. Scheme is top notch in this regard as the standards do not specify a stack, meaning that implementations can do things like heap allocate stack frames that grow and shrink according to demand.
a3voices 11y ago
I often fail recursion questions during interviews because I don't like thinking about recursion. It's too stupid and pointless to think about.
- ludamad 11y ago
  Even when working with trees?
  - a3voices 11y ago
    Why would you ever work on the internals of how trees work? That has 0 business value 99.99% of the time. It's all solved problems. And even so recursion might not be the best approach.
    - barrkel 11y ago
      If you ever develop any abstraction over the raw DOM when writing a rich web app, you'll be dealing with trees, and if your abstraction supports nesting, you'll be dealing with recursion.
      - douche 11y ago
        Because we don't have enough new JavaScript front-end frameworks coming out every week.
    - baddox 11y ago
      Trees don't always call themselves "trees." They can sneak up on you. Nested lists, for instance, are equivalent to trees, and nested lists show up all the time. Perhaps your programming languages has some sort of recursive map function builtin, but a lot of common languages don't, and it really helps to be able to intuitively think about recursive traversal.
    - akamel 11y ago
      when did the dumbing down of programming start? I'm all for code-reuse and componentization but common... recursion is programming 101!
myth_buster 11y ago
You are not alone. NASA/JPL explicitly prohibits it in their coding standards [0]. Rule 4 (recursion) There shall be no direct or indirect use of recursive function calls. [MISRA-C:2004 Rule 16.2; Power of Ten Rule 1] The presence of statically verifiable loop bounds and the absence of recursion prevent runaway code, and help to secure predictable performance for all tasks. The absence of recursion also simplifies the task of deriving reliable bounds on stack use. The two rules combined secure a strictly acyclic function call graph and control-flow structure, which in turn enhances the capabilities for static checking tools to catch a broad range of coding defects. [0] http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf
- bunderbunder 11y ago
  Though, for context, here's the first paragraph after the introduction: The coding rules defined here primarily target the development of mission critical flight software written in the C programming language. This means that the rules are focused on embedded software applications, which generally operate under stricter resource constraints than, e.g., ground software. I don't think it's at all surprising that the coding standards governing critical software running in resource-constrained environments should be so conservative. But I also don't know that the priorities motivating those standards generalize well to what most programmers do for a living.
- Jtsummers 11y ago
  Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack. In the embedded world we have to know how much space things need. You'll note they also ban malloc. But few would suggest that every C programmer should abandon malloc in their software.
  - cbd1984 11y ago
    > Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack. Only if you're sloppy about the inputs given to the recursive code. Recursion isn't magical. It's deterministic, and is a function of some aspect of the input values. (Corollary: If it isn't, what the fuck are you doing?) So NASA decided to solve the stack growth problem by limiting recursion. (Zero is a limit.) It could have done the other thing and limited inputs to recursive code, which would have required more careful code analysis (static and dynamic) to figure out what the limits should be. It's an understandable decision, but don't forget it's a trade-off, and one that could have gone another way.
com2kid 11y ago
> It's my uninformed opinion that recursion is uninteresting and unintuitive. Recursion is the use of the built in stack data structure that the compiler manages for you. If you are working your way through a data set with a well determined end state that you incrementally approach (be it the end of the list, or getting closer and closer to finding a value in a tree), and you have a need to backtrack, then recursion is a good way to solve the problem. All recursive code can be rewritten to be non-recursive, you just keep track of your own stack data structure. This can be either not that much work, or a major pain, depending on the exact problem.
- Something1234 11y ago
  > All recursive code can be rewritten to be non-recursive, you just keep track of your own stack data structure. This can be either not that much work, or a major pain, depending on the exact problem. Bull, a function that is not primitive recursive cannot be rewritten to be non recursive. Sources: https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function https://www.youtube.com/watch?v=i7sm9dzFtEI https://www.youtube.com/watch?v=i7sm9dzFtEI
cossatot 11y ago
> It's my uninformed opinion that recursion is uninteresting and unintuitive. It's my informed opinion that I personally often find unintuitive things to be uninteresting, because thinking about them is less rewarding. I wouldn't take your lack of interest to be a sign of your lack of intelligence so much as a different distribution of intuition.
bbcbasic 11y ago
I agree, I don't think I have ever used recursion in production code. You can normally avoid it by using a queue or stack data structure. Or rethinking the problem. Haskell tutorials usually advise against explicit recursion, instead favouring combinations of map, filter etc. as the best choice, and failing that use foldl', foldr etc. With explicit recursion only being used if you really have a good reason.

by dvt 11y ago

rblatz 11y ago

I'm fairly sure Dijkstra didn't say that, since he was advocating for recursion to be added. It was one of the splinter Algol groups that added that sentence trying to remove it.

dvt 11y ago
Whoops, I misunderstood, had to re-read that paragraph :)
- rblatz 11y ago
  No worries, I reread it multiple times to make sure I had it right. Not the clearest paragraph.

baddox 11y ago

I find recursion extremely intuitive, if not necessary, for pretty much any data structure with a bunch of things ("nodes") pointing to other things. That includes, most notably, linked lists and trees. I can probably work up recursive pseudocode for tree traversals pretty easily, despite not having studied computer science or doing it at work for several years, yet I find an iterative solution somewhat elusive and unnatural.

dvt 11y ago
Different strokes for different folks, as they say.
- baddox 11y ago
  I agree, but do you really think of a binary tree traversal iteratively? I won't say it's wrong, but I am extremely surprised.
  - erikpukinskis 11y ago
    It depends somewhat on what you are doing. If you are on a walk through a (metaphorical) forest, do you think of yourself on a subpath of a subpath of a subpath, or is it just "well I guess I'm here now!"? If you are just doing a simple search, maybe you don't need to keep that whole stack around. An iterative approach makes a lot of sense. If you are building a map of the tree and you're not even sure what scale to make it, you might want to reserve judgement about the supertree while you explore some sub trees so you might be glad that stack is there, and you might profit from thinking about that situation as recursion. But the answer is: yes, a lot of things you do with trees make a lot of sense as simple procedures.
  - dvt 11y ago
    No, I think about it recursively. But it hurts my brain. And to be fair, tree traversal is one of the things I find pretty intuitive about recursion. Other stuff, not so much. Consider the Fibonacci Sequence written recursively.
    - davexunit 11y ago
      The recursive definition is intuitive and easy to come up with given its mathematical definition. To avoid redundant computation, the function can be memoized. Yes, you can write it linearly as well, but oftentimes the linear algorithm is harder to come up with. SICP spends a lot of time on this subject in one of its early chapters and its worth a read. Also, some languages support recursion better than others. Scheme is top notch in this regard as the standards do not specify a stack, meaning that implementations can do things like heap allocate stack frames that grow and shrink according to demand.

a3voices 11y ago

I often fail recursion questions during interviews because I don't like thinking about recursion. It's too stupid and pointless to think about.

ludamad 11y ago
Even when working with trees?
- a3voices 11y ago
  Why would you ever work on the internals of how trees work? That has 0 business value 99.99% of the time. It's all solved problems. And even so recursion might not be the best approach.
  - barrkel 11y ago
    If you ever develop any abstraction over the raw DOM when writing a rich web app, you'll be dealing with trees, and if your abstraction supports nesting, you'll be dealing with recursion.
    - douche 11y ago
      Because we don't have enough new JavaScript front-end frameworks coming out every week.
  - baddox 11y ago
    Trees don't always call themselves "trees." They can sneak up on you. Nested lists, for instance, are equivalent to trees, and nested lists show up all the time. Perhaps your programming languages has some sort of recursive map function builtin, but a lot of common languages don't, and it really helps to be able to intuitively think about recursive traversal.
  - akamel 11y ago
    when did the dumbing down of programming start? I'm all for code-reuse and componentization but common... recursion is programming 101!

myth_buster 11y ago

You are not alone. NASA/JPL explicitly prohibits it in their coding standards [0]. Rule 4 (recursion) There shall be no direct or indirect use of recursive function calls. [MISRA-C:2004 Rule 16.2; Power of Ten Rule 1] The presence of statically verifiable loop bounds and the absence of recursion prevent runaway code, and help to secure predictable performance for all tasks. The absence of recursion also simplifies the task of deriving reliable bounds on stack use. The two rules combined secure a strictly acyclic function call graph and control-flow structure, which in turn enhances the capabilities for static checking tools to catch a broad range of coding defects. [0] http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

bunderbunder 11y ago
Though, for context, here's the first paragraph after the introduction: The coding rules defined here primarily target the development of mission critical flight software written in the C programming language. This means that the rules are focused on embedded software applications, which generally operate under stricter resource constraints than, e.g., ground software. I don't think it's at all surprising that the coding standards governing critical software running in resource-constrained environments should be so conservative. But I also don't know that the priorities motivating those standards generalize well to what most programmers do for a living.
Jtsummers 11y ago
Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack. In the embedded world we have to know how much space things need. You'll note they also ban malloc. But few would suggest that every C programmer should abandon malloc in their software.
- cbd1984 11y ago
  > Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack. Only if you're sloppy about the inputs given to the recursive code. Recursion isn't magical. It's deterministic, and is a function of some aspect of the input values. (Corollary: If it isn't, what the fuck are you doing?) So NASA decided to solve the stack growth problem by limiting recursion. (Zero is a limit.) It could have done the other thing and limited inputs to recursive code, which would have required more careful code analysis (static and dynamic) to figure out what the limits should be. It's an understandable decision, but don't forget it's a trade-off, and one that could have gone another way.

com2kid 11y ago

> It's my uninformed opinion that recursion is uninteresting and unintuitive. Recursion is the use of the built in stack data structure that the compiler manages for you. If you are working your way through a data set with a well determined end state that you incrementally approach (be it the end of the list, or getting closer and closer to finding a value in a tree), and you have a need to backtrack, then recursion is a good way to solve the problem. All recursive code can be rewritten to be non-recursive, you just keep track of your own stack data structure. This can be either not that much work, or a major pain, depending on the exact problem.

Something1234 11y ago
> All recursive code can be rewritten to be non-recursive, you just keep track of your own stack data structure. This can be either not that much work, or a major pain, depending on the exact problem. Bull, a function that is not primitive recursive cannot be rewritten to be non recursive. Sources: https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function https://www.youtube.com/watch?v=i7sm9dzFtEI https://www.youtube.com/watch?v=i7sm9dzFtEI

cossatot 11y ago

> It's my uninformed opinion that recursion is uninteresting and unintuitive. It's my informed opinion that I personally often find unintuitive things to be uninteresting, because thinking about them is less rewarding. I wouldn't take your lack of interest to be a sign of your lack of intelligence so much as a different distribution of intuition.

bbcbasic 11y ago

I agree, I don't think I have ever used recursion in production code. You can normally avoid it by using a queue or stack data structure. Or rethinking the problem. Haskell tutorials usually advise against explicit recursion, instead favouring combinations of map, filter etc. as the best choice, and failing that use foldl', foldr etc. With explicit recursion only being used if you really have a good reason.