The reasons I avoid recursion don’t align with saving memory. I avoid recursion primarily to make it easier to read the code. Recursion requires you to keep track of the implicit stack, an explicit stack makes that easier for me.
Secondarily, I don’t want to deal the administrative work the author says I should do in a recursive situation, as allocating the stack size would happen far away from my algorithm, making it another thing to go hunt down when my memory usage grows, instead of a local memory allocation.
And thirdly, there can be a cost to calling functions that has been significant for me. I have a much better feel for how a loop will perform than a recursive call tree. Maybe the optimizer will do something with it, maybe it won’t. Maybe I’ll make a minor change and the optimizer will stop working and I’m getting a tenth the speed I should.
I will prototype algorithms recursively sometimes, but usually it’s very simple to convert them back into a loop with explicit stack, and many times that stack isn’t even needed. So I hardly leave it in.
> The reasons I avoid recursion don’t align with saving memory. I avoid recursion primarily to make it easier to read the code. Recursion requires you to keep track of the implicit stack, an explicit stack makes that easier for me.
If you read for example "The Little Schemer", it will teach you to think about recursion in a way, that you do not actually keep track of the stack in your mind implicitly. To not think this way is actually key to understand some recursive programs. I think this has also been in one of the SICP lectures or talked about by one of the authors.
> Secondarily, I don’t want to deal the administrative work the author says I should do in a recursive situation, as allocating the stack size would happen far away from my algorithm, making it another thing to go hunt down when my memory usage grows, instead of a local memory allocation.
> At the same time, recursion does not lead to particularly bad performance in Racket, and there is no such thing as stack overflow; you can run out of memory if a computation involves too much context, but exhausting memory typically requires orders of magnitude deeper recursion than would trigger a stack overflow in other languages. These considerations, combined with the fact that tail-recursive programs automatically run the same as a loop, lead Racket programmers to embrace recursive forms rather than avoid them.
And about:
> And thirdly, there can be a cost to calling functions that has been significant for me.
This is a compiler specific thing. A good compiler can turn a tail-recursive function to run the same as a loop, no additional cost for any function calls (also see the quoted Racket docs).
> I will prototype algorithms recursively sometimes, but usually it’s very simple to convert them back into a loop with explicit stack, and many times that stack isn’t even needed. So I hardly leave it in.
Yes. It is mostly a simple conversion from a recursive definition to a loop definition. However, you would be surprised how many programmers do not know how to do this or have never done this, because languages they learned have merely taught them to fear recursion and so they never really wrote recursive functions much.
Also couples very elegantly with pattern matching in Erlang. Also great in SML. Makes me sometimes thing I should be doing more pattern matching in my projects in Scheme. But matching types in pattern matching does add to it even more.
I read The Little Schemer, twice! It's a wonderful fun book that I recommend to anyone.
When I'm going through the book and playing around with Scheme I "get" recursion. Then I put the book down and go back to "real" programming and somehow this just gets lost.
Maybe it's just a matter of more practice, but it's never come naturally to me.
Dijkstra famously wrote that "it is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Once you get used to it, the overwhelming majority of cases you don't actually need to manually write recursive style functions - you start thinking in terms of `map`, `zip`, `unzip` `fold`, `unfold`, `scan`, `init`, `filter`, `take` and `drop`. There are various other related methods but they can usually all be implemented in terms of these. As for non-recursive styles of iteration, I use F# as my primary language and every time I write a loop I have to consult the manual to remind myself of the exact syntax because it's so rare that I actually use them. Usually `iter` does the trick.
"Regular" functional programming is fine, mostly it's just "apply a function to a list of values" (things like fold, which seems like reduce, is a bit more involved, but not much).
It's the "factorial in recursive style" type of stuff that trips me up. I can read imperative code like I would read a book: I just do (assuming I'm familiar with the language), but this sort of recursive stuff just trips me up, never mind actually writing it.
I'm very glad to have gone through the functional programming canon, it has certainly impacted my thinking on things for my whole career, but I still prefer it be explicit if I'm relying on a stack.
> there can be a cost to calling functions that has been significant for me
Have you measured? Function call overhead is one of those things people usually feel is expensive, but in 99.9% of cases, isn't, especially when adjusting for whether optimizations from avoiding calls come from inlining instead of avoiding the actual call instructions, and especially when the function call is direct, not through a table/PLT/etc.. Worrying about function calls is up there with juggling thread priorities and replacing multiplies with shifts in the ranks of performance superstition and woo.
I’ve hit the cliff once. That’s why it’s last on the list. It’s not very often, but it is possible to hit and with the other reasons and the ease of avoiding it make it easy to justify the very small (if any) amount of work to avoid recursion most of the time.
Secondarily, I don’t want to deal the administrative work the author says I should do in a recursive situation, as allocating the stack size would happen far away from my algorithm, making it another thing to go hunt down when my memory usage grows, instead of a local memory allocation.
And thirdly, there can be a cost to calling functions that has been significant for me. I have a much better feel for how a loop will perform than a recursive call tree. Maybe the optimizer will do something with it, maybe it won’t. Maybe I’ll make a minor change and the optimizer will stop working and I’m getting a tenth the speed I should.
I will prototype algorithms recursively sometimes, but usually it’s very simple to convert them back into a loop with explicit stack, and many times that stack isn’t even needed. So I hardly leave it in.