5 ms·
> 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 t
by zelphirkalt 3y ago
> 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.
This is a language specific concern. Look for example at the Racket docs: https://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html https://docs.racket-lang.org/guide/Lists__Iteration__and_Rec...:
> 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.
- macintux 3y agoI was on the fence wrt recursion until I met Erlang, which is recursion all the way down. The language you use makes a world of difference.
- zelphirkalt 3y agoAlso 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.
- arp242 3y agoI 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." I started with BASIC. Maybe Dijkstra was right.
- sparkie 3y agoOnce 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.
- arp242 3y ago"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.
- rmckayfleming 3y agoWhat do you mean "factorial in recursive style"? Like recursive with an accumulator?
- sanderjd 3y agoI'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.