10 ms·

How often do recursive functions come up in your daily programming life? For me they're rare enough that it makes sense that many otherwise competent developers

How often do recursive functions come up in your daily programming life? For me they're rare enough that it makes sense that many otherwise competent developers draw a blank when asked to write one in the context of a high-stress interview. They may look clever, but they're often not the ideal solution compared to a simpler to understand, and often easier to optimise iterative solution. I write plenty of DSP, GPGPU programming, and computer vision, and I can't honestly remember the last time I wrote a recursive function.

dekhn 6y ago
They come up about once a year for me. That's about how often I have to write a tree traversal.
- sukilot 6y ago
  Why traverse a tree recursively and risk blowing your stack?
  - dekhn 6y ago
    Hmm, let's see. The last time I blew the computer's stack due to tree recursion was in 1995 (it was six levels deep). Since then, I've never seen a stack overflow due to tree recursion (presumably because none of the trees I've operated on were deeper than the hardware stack, and I switched from C to Python where the stack is far, far deeper). If I were writing a server that needed better memory requirements, I could certainly transform my code if desired.
  - mlyle 6y ago
    You'd sure need a pretty tiny stack and/or an unbelievable amount of context on stack to worry too much about this. If our per-callstack frame is 10k bytes, and we can spend 1 megabyte of stack on recursion (both are pessimistic).. we can go 100 levels deep. Which means we can expect to run into problems when there are more than ~5E29 elements. This assumes we don't write the recursion in a way that the compiler can elide it entirely with tail-call optimization. I'm not a huge fan of recursion, but let's not resort to too much hyperbole in our arguments against it. :P
    - dekhn 6y ago
      On my 1995 DOS-based computer, the C compiler I used at the time could handle roughly 6 levels deep.
      - mlyle 6y ago
        Probably you were limited to a single 64k segment for stack... still would have required a really big amount of context per call to blow stack so quickly. Back in the mid 80's on DOS I had no problem recursing 30+ levels deep.
    - joefourier 6y ago
      I have 20KB total RAM on the MCU I'm currently programming for. It's not too hyperbolic to imagine real-world cases where some recursive functions would be unsuitable. They're handy for some parsing and scripting scenarios however, I'll grant you that.
    - jlokier 6y ago
      > If our per-callstack frame is 10k bytes, and we can spend 1 megabyte of stack on recursion (both are pessimistic).. we can go 100 levels deep. Which means we can expect to run into problems when there are more than ~5E29 elements. This is incorrect. Your limit is only for fully balanced trees. On a fully unbalanced tree your solution will crash at about 100 elements. Do we see a lot of unbalanced trees? Yes, most of the time in my experience. If there's a balanced tree, there's probably a data structure and the function is already supplied. Writing a tree traversal function come up when working with unbalanced things like program ASTs, JSON/HTML/XML parsed data, Lisp-style lists, filesystem traversal, etc. > This assumes we don't write the recursion in a way that the compiler can elide it entirely with tail-call optimization. The compiler cannot elide away tree traversal with tail-call optimisation. Only one branch. A really smart compiler could transform it into a loop with an explicit node-stack using an array, or avoid the stack and use in-place pointer-reversal if concurrency rules permit and there's a spare bit. But I've never seem a really smart compiler do either of those things.
      - mlyle 6y ago
throwaway_pdp09 6y ago
> I write plenty of DSP, GPGPU programming, and computer vision ... I can't honestly remember the last time I wrote a recursive function. Not remotely surprising is it. Hopefully if you went for a suitable job they wouldn't ask unsuitable questions. Then again, writing a recursive factorial should pain no-one.
- dhosek 6y ago
  Exactly. I wasn't asking people to do something difficult. I don't think that there's a simpler recursive function than this, if you can't do this, then you don't have basic knowledge of what a recursive function is. I learned how to do this in high school.
lmilcin 6y ago
It is not about how often they come up but whether you can think in an abstract way on a convoluted problem. Think about IQ test which shows some abstract puzzles that have no connection with the real world. They are part of the test because they provide measurement points on tasks that require different types of abstract thinking without prerequisite knowledge. Again, it is not possible to verify you have all the necessary knowledge for the job, nor would it be useful (no candidate knows everything for the position and if he did he would likely be overqualified). I of course ask questions that test candidate's knowledge in the most useful areas, but at least part of the interview I want to devote to finding out how smart he/she is on abstract tasks that don't require some special knowledge.
- sukilot 6y ago
  I don't want to let abstract convoluted problem solvers anywhere near my production systems
  - mlyle 6y ago
    You probably want to avoid people with a propensity for viewing things in abstract and convoluted terms... not to avoid people with the ability to solve abstract and/or convoluted problems.
sukilot 6y ago
Recursive functions come up quite often when investigating the root cause of outages. Unclear if that means we need candidates who are better at recursion, or better at avoiding recursion.
dhosek 6y ago
Recursion is pretty fundamental in functional programming—it's preferred over loops. A smart compiler will do tail-call optimization and eliminate the overhead of increasing the stack size. Even if you're working in a non-FP development environment, knowledge of FP techniques makes one a stronger programmer. And recursion is not some esoteric technique in any event.

dekhn 6y ago

They come up about once a year for me. That's about how often I have to write a tree traversal.

sukilot 6y ago
Why traverse a tree recursively and risk blowing your stack?
- dekhn 6y ago
  Hmm, let's see. The last time I blew the computer's stack due to tree recursion was in 1995 (it was six levels deep). Since then, I've never seen a stack overflow due to tree recursion (presumably because none of the trees I've operated on were deeper than the hardware stack, and I switched from C to Python where the stack is far, far deeper). If I were writing a server that needed better memory requirements, I could certainly transform my code if desired.
- mlyle 6y ago
  You'd sure need a pretty tiny stack and/or an unbelievable amount of context on stack to worry too much about this. If our per-callstack frame is 10k bytes, and we can spend 1 megabyte of stack on recursion (both are pessimistic).. we can go 100 levels deep. Which means we can expect to run into problems when there are more than ~5E29 elements. This assumes we don't write the recursion in a way that the compiler can elide it entirely with tail-call optimization. I'm not a huge fan of recursion, but let's not resort to too much hyperbole in our arguments against it. :P
  - dekhn 6y ago
    On my 1995 DOS-based computer, the C compiler I used at the time could handle roughly 6 levels deep.
    - mlyle 6y ago
      Probably you were limited to a single 64k segment for stack... still would have required a really big amount of context per call to blow stack so quickly. Back in the mid 80's on DOS I had no problem recursing 30+ levels deep.
  - joefourier 6y ago
    I have 20KB total RAM on the MCU I'm currently programming for. It's not too hyperbolic to imagine real-world cases where some recursive functions would be unsuitable. They're handy for some parsing and scripting scenarios however, I'll grant you that.
  - jlokier 6y ago
    > If our per-callstack frame is 10k bytes, and we can spend 1 megabyte of stack on recursion (both are pessimistic).. we can go 100 levels deep. Which means we can expect to run into problems when there are more than ~5E29 elements. This is incorrect. Your limit is only for fully balanced trees. On a fully unbalanced tree your solution will crash at about 100 elements. Do we see a lot of unbalanced trees? Yes, most of the time in my experience. If there's a balanced tree, there's probably a data structure and the function is already supplied. Writing a tree traversal function come up when working with unbalanced things like program ASTs, JSON/HTML/XML parsed data, Lisp-style lists, filesystem traversal, etc. > This assumes we don't write the recursion in a way that the compiler can elide it entirely with tail-call optimization. The compiler cannot elide away tree traversal with tail-call optimisation. Only one branch. A really smart compiler could transform it into a loop with an explicit node-stack using an array, or avoid the stack and use in-place pointer-reversal if concurrency rules permit and there's a spare bit. But I've never seem a really smart compiler do either of those things.
    - mlyle 6y ago

throwaway_pdp09 6y ago

> I write plenty of DSP, GPGPU programming, and computer vision ... I can't honestly remember the last time I wrote a recursive function. Not remotely surprising is it. Hopefully if you went for a suitable job they wouldn't ask unsuitable questions. Then again, writing a recursive factorial should pain no-one.

dhosek 6y ago
Exactly. I wasn't asking people to do something difficult. I don't think that there's a simpler recursive function than this, if you can't do this, then you don't have basic knowledge of what a recursive function is. I learned how to do this in high school.

lmilcin 6y ago

It is not about how often they come up but whether you can think in an abstract way on a convoluted problem. Think about IQ test which shows some abstract puzzles that have no connection with the real world. They are part of the test because they provide measurement points on tasks that require different types of abstract thinking without prerequisite knowledge. Again, it is not possible to verify you have all the necessary knowledge for the job, nor would it be useful (no candidate knows everything for the position and if he did he would likely be overqualified). I of course ask questions that test candidate's knowledge in the most useful areas, but at least part of the interview I want to devote to finding out how smart he/she is on abstract tasks that don't require some special knowledge.

sukilot 6y ago
I don't want to let abstract convoluted problem solvers anywhere near my production systems
- mlyle 6y ago
  You probably want to avoid people with a propensity for viewing things in abstract and convoluted terms... not to avoid people with the ability to solve abstract and/or convoluted problems.

sukilot 6y ago

Recursive functions come up quite often when investigating the root cause of outages. Unclear if that means we need candidates who are better at recursion, or better at avoiding recursion.

dhosek 6y ago

Recursion is pretty fundamental in functional programming—it's preferred over loops. A smart compiler will do tail-call optimization and eliminate the overhead of increasing the stack size. Even if you're working in a non-FP development environment, knowledge of FP techniques makes one a stronger programmer. And recursion is not some esoteric technique in any event.