4 ms·

Maybe it's just that I'm not writing code as complicated as you, but 5 years of school and 5 years of industry, I've never had to hold more than a single level

Maybe it's just that I'm not writing code as complicated as you, but 5 years of school and 5 years of industry, I've never had to hold more than a single level of a function in my head at once. My trick is to explicitly say what contract the function fulfills, i.e. if the input has X property, then the output has Y property. Then when you make the recursive call, you can just assume your called function behaves as advertised. I thought this was the whole point of recursion.

lhnz 10y ago
What you're describing is how normal functions are generally written. If there is no difference in complexity between writing a function that calls itself and a function that just computes some data and returns it then surely this discussion wouldn't be happening. I think it's happening for a reason so I tried to articulate this. I'm speculating that recursive solutions are more difficult for people to write, because (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'), (3) the function calls each relate to each other and likewise so do their values, but this mapping is generally not expressed well within the code or within outputs you might debug (after each function application, a value is received for which the context of how it was produced is often lost.) I'm probably speaking in too abstract a way to be clear. I think the tools could be improved here; I was thinking about the problem earlier on and I realised that generally I solve it by breaking the problems up into tiny functions [0]. Unfortunately, there's a time cost to this approach, so I would prefer it if debugging tools would instead allow you to annotate blocks of code. They could then represent this information visually. This would help me. I also think that good teaching is important. I remember that I used to be utterly terrible at writing these functions: my main issue was often that I didn't start by thinking about the 'base case' and the simplest inputs. That's easy to get right. I do think that my mind has never been very well suited to recursive computation, however I believe I'm decent at understanding and problem-solving around this. It's because I have to think carefully and tool myself when dealing with recursive problems, that I'm able to describe the pitfalls. I have never been the kind of person to compel myself into understanding something merely by stating "this is easy". [0] https://twitter.com/nouswaves/status/776384680652398592 https://twitter.com/nouswaves/status/776384680652398592
- drbawb 10y ago
  In a way I find recursive functions _reduce_ the complexity required to reason about a loop. What made me grok recursion was realizing that it's just a more explicitly defined loop: - You have to define an end condition. (Really this is no different than the 2nd clause of a C-style for() loop, or the expression evaluated by a `while()` loop.) - You have to explicitly specify the inputs for each iteration of the loop (e.g: explicitly declare what you need in the function signature, instead of just using whatever variables happen to be in the parent scope as working memory.) - It makes optimization concerns very quickly apparent, as you'll pretty quickly blow the stack or start waiting for the heat-death of the universe. The best heuristics I have for a quick optimization pass are: is it tail-recursive, and does it needlessly recompute values? Once I realized recursion is just another way to tell the compiler "repeat this thing until [x] is true", it became a lot less mystical and much easier to reason about. I'd agree with OP to an extent that syntax did make a huge difference in how I viewed recursion. I understood recursion on a theoretical level for a while, but avoided it whenever possible because I too thought it was difficult to reason about. It wasn't until I learned Elixir that it "clicked" for me. Between pattern matching and multiple function heads: Elixir just made recursion really easy to think about. (Not having any traditional loop construct probably helped a bit, too.)
  - lhnz 10y ago
    I agree with you that it is more explicit than looping: I actually think that with complicated logic, loops suffer from even worse problems, and for simple things most people just `filter`, `reduce` or `map`. That said, I do think the debuggability could be improved.
  - rrdharan 10y ago
    This is a really nice way to think about recursion! Thanks for sharing it.
- wz1000 10y ago
  > (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'), These aren't issues as long as you can prove your recurrence relation is correct. If you treat the recursive call as a black box, there is no reason to think about how it actually behaves and computes its result.

lhnz 10y ago

What you're describing is how normal functions are generally written. If there is no difference in complexity between writing a function that calls itself and a function that just computes some data and returns it then surely this discussion wouldn't be happening. I think it's happening for a reason so I tried to articulate this. I'm speculating that recursive solutions are more difficult for people to write, because (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'), (3) the function calls each relate to each other and likewise so do their values, but this mapping is generally not expressed well within the code or within outputs you might debug (after each function application, a value is received for which the context of how it was produced is often lost.) I'm probably speaking in too abstract a way to be clear. I think the tools could be improved here; I was thinking about the problem earlier on and I realised that generally I solve it by breaking the problems up into tiny functions [0]. Unfortunately, there's a time cost to this approach, so I would prefer it if debugging tools would instead allow you to annotate blocks of code. They could then represent this information visually. This would help me. I also think that good teaching is important. I remember that I used to be utterly terrible at writing these functions: my main issue was often that I didn't start by thinking about the 'base case' and the simplest inputs. That's easy to get right. I do think that my mind has never been very well suited to recursive computation, however I believe I'm decent at understanding and problem-solving around this. It's because I have to think carefully and tool myself when dealing with recursive problems, that I'm able to describe the pitfalls. I have never been the kind of person to compel myself into understanding something merely by stating "this is easy". [0] https://twitter.com/nouswaves/status/776384680652398592 https://twitter.com/nouswaves/status/776384680652398592

drbawb 10y ago
In a way I find recursive functions _reduce_ the complexity required to reason about a loop. What made me grok recursion was realizing that it's just a more explicitly defined loop: - You have to define an end condition. (Really this is no different than the 2nd clause of a C-style for() loop, or the expression evaluated by a `while()` loop.) - You have to explicitly specify the inputs for each iteration of the loop (e.g: explicitly declare what you need in the function signature, instead of just using whatever variables happen to be in the parent scope as working memory.) - It makes optimization concerns very quickly apparent, as you'll pretty quickly blow the stack or start waiting for the heat-death of the universe. The best heuristics I have for a quick optimization pass are: is it tail-recursive, and does it needlessly recompute values? Once I realized recursion is just another way to tell the compiler "repeat this thing until [x] is true", it became a lot less mystical and much easier to reason about. I'd agree with OP to an extent that syntax did make a huge difference in how I viewed recursion. I understood recursion on a theoretical level for a while, but avoided it whenever possible because I too thought it was difficult to reason about. It wasn't until I learned Elixir that it "clicked" for me. Between pattern matching and multiple function heads: Elixir just made recursion really easy to think about. (Not having any traditional loop construct probably helped a bit, too.)
- lhnz 10y ago
  I agree with you that it is more explicit than looping: I actually think that with complicated logic, loops suffer from even worse problems, and for simple things most people just `filter`, `reduce` or `map`. That said, I do think the debuggability could be improved.
- rrdharan 10y ago
  This is a really nice way to think about recursion! Thanks for sharing it.
wz1000 10y ago
> (1) whether a function is said to have worked or not could be dependent on a call multiple levels deep from the original call, (2) the immutable constant named `foo` you created within the function body might contain different values at every deeper call (therefore it is no longer an effective name to refer to 'one thing'), These aren't issues as long as you can prove your recurrence relation is correct. If you treat the recursive call as a black box, there is no reason to think about how it actually behaves and computes its result.