[HN Gopher] How to Get Better at Recursion
___________________________________________________________________
How to Get Better at Recursion
Author : eatonphil
Score : 35 points
Date : 2021-03-07 16:41 UTC (6 hours ago)
(HTM) web link (notes.eatonphil.com)
(TXT) w3m dump (notes.eatonphil.com)
| roberto wrote:
| There's some good discussion about the topic here:
| https://news.ycombinator.com/item?id=26377312
| imperistan wrote:
| Good one :)
| peterkelly wrote:
| All the examples are tail recursive, which is exactly equivalent
| to looping. All you're going to achieve by doing this is to get
| an inaccurate understanding of what recursion actually is.
|
| Practicing working with true recursion would involve algorithms
| that are not tail-recursive, such as tree traversal.
|
| Just read SICP. You can thank me later.
| lmilcin wrote:
| Still, even when tail recursive it is useful when it ends up
| with clean code. But then if you want to read it you still have
| to understand what it is tail recursion and whether it applies
| in particular case.
| 8note wrote:
| A nice thing about tail recursion is having a in interface
| for what the loop requires at the start.
|
| Putting a function call in a loop maybe does that more
| clearly though
| marshmallow_12 wrote:
| how to get better at recursion: see _how to get better at
| recursion_.
|
| carry on now...
| primaryobjects wrote:
| Practicing dynamic programming algorithms is also an excellent
| way to get better at recursion (and recurrences).
|
| Even better, dynamic programming is often more production worthy,
| since it can result in improved time complexity.
| Naac wrote:
| Could recursion be ( one of ) the reasons why ML and Scheme ( and
| lisp, clojure, etc. ) aren't popular as industry languages?
|
| I learned recursion in University, it's undeniably a foundational
| piece of Computer Science theory. I use recursion when I have to
| do interview problems. And I think that's about it.
|
| The number of times I actually used recursion in production was
| maybe twice. And one of those times the PR was rejected. In my
| experience the overhead of understanding the code outweighs its
| terseness. This is also how I sometimes feel about macros in
| clojure. The cons outweigh the pros.
| agumonkey wrote:
| IMO vaguely, lisps and ml are disqualified way earlier.
|
| Lisps don't even pass the syntax phase.. newcomers won't have
| the tool-magic dopamine hook (say the first time you saw PHP
| map syntax, or ruby blocks or c# interop features). That's what
| people love at first, it gives a sense of a large new universe
| of powers.. while lisp is a naked white page of parens.. people
| just don't see what it's for. Other people will click on the
| deeper uniformity and lack of syntax as a lever.
|
| Same goes for fp.. people see a soup of function, it's
| meaningless. Again the syntax hook is strong and instead of
| having f . g . h you get @f.then(g)[[h]] the brain gets tickled
| differently.
| dehrmann wrote:
| Maybe, but I don't see it as "recursion is hard," I see it as
| lisps being more clever than pragmatic.
| Jtsummers wrote:
| At least Common Lisp, Racket, and Clojure seem more pragmatic
| than clever to me. How are they "more clever than pragmatic"
| in your opinion?
| andi999 wrote:
| Probably the other PR just slipped through... What I find
| difficult with recursion in practice is that the stack depth is
| quite limited, also depending from what stack depth you are
| calling the function. Of course memory can also blowup but this
| is easier to reason (and adding 128gig might just solve it)
| mrkeen wrote:
| Stack-depth is an implementation detail.
|
| It's chicken-and-egg. Programmers think of recursion as that
| thing that blows up the stack, so they don't demand that
| language implementers do a better job with it. Language
| implementers don't stop recursion from blowing up the stack
| because no-one is asking them to do so.
| andi999 wrote:
| Yes. So you cannot use it in production.
| peterkelly wrote:
| Have you ever
|
| - Traversed a directory hierarchy to compute the total size or
| other statistics about its contents?
|
| - Searched for a DOM element on a web page matching certain
| criteria _without_ using third-party libraries or helper
| functions like querySelector()?
|
| - Implemented a hierarchical navigation structure in a user
| interface?
|
| - Work on parts of a compiler/interpreter or other code that
| has to deal with formal language?
|
| - Written a parser for a file format that contains arbitrarily
| nested data structures (e.g. HTML/JSON)?
|
| - Done _anything_ with trees?
|
| - Solved a problem by breaking it down into smaller versions of
| the same problem, solving those, and then combining the
| results?
|
| I know that for lots of programming tasks recursion is not
| needed, but I'm genuinely curious as to what kind of software
| you work on where you've never encountered a problem that
| requires a recursive solution?
| vishnugupta wrote:
| I've been working mostly in the payments domain for the last
| 16 years. 90% backend, 10% web frontend.
|
| So far, I've had write recursive code just once to convert
| SOAP requests/response to REST request/response on the fly so
| that the test cases that were written using SOAP client could
| be reused to test REST end point as well.
|
| To state the obvious, the chances of encountering recursive
| code depends on the domain. In my experience though a typical
| CRUD business app won't require a recursion as you pointed
| out. The examples you sited are mostly encountered in a
| "framework" code (e.g., Spring, some UI framework) and as is
| typically the case the number of developers "using" a
| framework is an order of magnitude more than those who
| implement/maintain them. Same is the case with compiler. On
| the other hand, those who deal with the lower level system
| code (OS Kernel, RTOS etc.,) shun recursion altogether to
| avoid its unpredictable stack need. So in the spectrum of
| developers the band of coders who frequently deal with or
| encounter recursion is quite narrow IMO.
|
| There are languages where recursion is the only construct
| available to deal with a collection of values so for those
| programmers recursive technique is a muscle memory. But I
| suspect there aren't as many professional users of such
| languages.
| lmilcin wrote:
| None of the above actually _require_ recursion.
|
| Some of the above problems have very neat recursive solution
| but the recursion is bad idea as it tends to various edge
| cases.
|
| For example, "write a parser for a file format that contains
| _arbitarily_ nested data strucutres ", is exactly a problem
| where you DO NOT want to use recursion, and the reason is
| that "arbitarily" part. What if there is 1000 levels? What if
| there is 100 thousand levels?
|
| DoS guys love these kinds of implementations. Just send very
| small, very well compressed payload and look how it all
| crashes and burns.
| Jtsummers wrote:
| You'd run into the same denial of service problem in an
| iterative solution with an explicit stack/data structure
| that can be grown arbitrarily as well. The only way to
| prevent such an attack is an explicit limit (perhaps
| calculated at run time based on system specs) which can be
| done with either a recursive or iterative implementation
| but requires deliberate awareness either way.
| lmilcin wrote:
| Fair point, but how frequently do you see recursive
| implementations that also pass information to track
| recursion depth and various other information to limit
| resource usage?
|
| Have you ever seen a recursive call that also tries to
| detect/break cycles in the data structure?
|
| I suspect the reason these things get left out the moment
| the developer decides on a recursive function is because
| it doesn't look nearly as much elegant then.
| pksebben wrote:
| :(){ :|:& };:
| sokoloff wrote:
| There are problems that are inherently tree-structured and
| where anything other than recursion feels wrong.
|
| "Process all the files in this directory structure, counting
| them and summing their size." Sure, you can solve that without
| recursing, but I'd trust a recursive algorithm to have fewer
| hidden bugs.
| junke wrote:
| At least the recursive version stops by blowing the control
| stack when there is a loop in the file system.
| moron4hire wrote:
| Yeah, every time I've written I recursive algorithm in the
| past, I've eventually had to come back and reimplement it as
| iterative. It's such that I no longer start the recursive
| approach anymore and go straight to iterative.
|
| The iterative solution is better in every regard. The state
| transitions are easier to see, and the sub procedures are
| easier to identify and split up, if necessary.
|
| I have a degree in Computer Science, I did extremely well in
| that degree program, and I understand algorithms very well. I
| don't get the fascination with recursion in CS theory. It's
| just hiding state on the stack frame. That's why it's such a
| terrible tool, not just for engineering, but for teaching as
| well. Every recursive solution has an iterative solution, even
| if it's just tossing your state into a Stack data structure you
| manage yourself on the heap. You'd think you'd want to call
| that out for students.
| dehrmann wrote:
| I only use recursion where it makes sense and I can guarantee
| O(log n) runs. Unbalanced tree? Iterate. Large graph? BFS.
| That said, I agree with another comment here that you're more
| likely to have a bug code where you're maintaining a stack by
| hand. Recursion is easier when it's the best fit for the
| problem.
| moron4hire wrote:
| Fundamentally disagree. Any bugs in the iterative approach
| are likely to be found during development on even the
| simplest of synthetic test data sets. But the recursive
| approach has a gigantic bug lying in wait for you to run
| more data than you originally anticipated: the stack
| overflow.
| dehrmann wrote:
| I used to proctor an on-site laptop coding test where
| part of the solution involved traversing a large digraph.
| Maybe 50% of candidates could do it on their own without
| a bug in 45 minutes. 15% of candidates knocked it out by
| the halfway mark. Not that this is the best use of
| recursion--both implementations still need to track
| visited nodes.
| andi999 wrote:
| The Forth is not strong with this one... (I am fully on your
| side btw)
| imoverclocked wrote:
| Some languages don't have loops but rather have very good
| tail-recursive semantics. In that case, nothing is hiding in
| the stack.
|
| Talking about loops vs recursion is interesting but it feels
| kinda like salt vs pepper to me. I like both and use both
| where appropriate.
|
| While we are on the topic of similarly misused constructs,
| .stream() pipelines in Java are often clear and concise but
| as they get longer and hide more stuff in the stream, a loop
| would make far more sense and provide a much smaller runtime
| complexity.
|
| Often, people will aspire to create "beautiful" code where
| they relate recursion/loops/streams/etc as something
| beautiful. In that vein, I don't really care if code is
| "ugly" but I do care if it's unmaintainable, needlessly slow
| or accidentally complex.
| moron4hire wrote:
| Yeah, one of my last favorite phrases is "elegant code".
| "Elegance" is an attribute I'd assign to a dinner party,
| not work.
| thebigspacefuck wrote:
| Math heads frequently use the term for proofs. I see it
| as carry over
| lmilcin wrote:
| I think the best way to master recursion is to think of it as a
| data structure stored on the actual stack.
|
| As you enter you are creating elements (state) and store it on
| the stack and as you exit you are reducing elements.
|
| When thinking this way you can notice a lot of interesting points
| about recursion.
|
| For example, a simple way to test if you can get away with tail
| recursion is if you can reduce elements as you enter. It means
| you don't have to store elements as you enter -- no need for data
| structure on the stack == no need for actual recursion.
|
| Another observation to remember is you can write that as an
| actual stack and implement any recursive problem (for example
| tree traversal) without recursion. Your data structure contains
| the state that you need.
|
| I would sometimes write recursive solution first and then see if
| it might be better off rewritten to use a separate stack and
| loop.
|
| Yet another important observation is that on a program stack you
| don't normally access anything than top of the stack. But for
| your algorithm having access to all previous levels might be
| useful. That's where writing it as a separate data structure
| might be advantageous.
| CJefferson wrote:
| The biggest problem with recursion in most languages is the
| maximum stack size is too small, so you end up banging against
| the limit when your problem gets big enough.
|
| In Rust I'm spinning up another thread just to run recursive
| algorithms in, which I give a huge (1/2 size physical memory)
| stack size for running recursive algorithms in.
| souprock wrote:
| Curious... does Rust require code to be marked unsafe when the
| maximum depth of recursion can't be proven to fit within the
| available stack? If not, it's a huge hole in the memory
| protection.
| yinzer-solomon wrote:
| IIRC, "Simply Scheme" describes several different recursion
| patterns, and it provides a number of exercises that match each
| pattern.
| eatonphil wrote:
| Thanks for sharing that! Hadn't heard of it. On my list now.
| barefeg wrote:
| Recursion is a two edge sword. Don't go rewriting everything
| recursively if you don't understand the requirements of the
| problem in the first place
| DaveSchmindel wrote:
| Or if you don't know what it entails, RE: space complexity
| issues within your runtime.
| sbrother wrote:
| Easiest way is probably to get a job at a company working a
| language that forces you to write recursive algorithms. I started
| my career at a startup where everything was Erlang, and a year of
| that made FAANG interviews a breeze with all the graph/DP
| problems.
| tmoertel wrote:
| One property that makes recursion attractive is that maps so
| easily to proof by induction. When designing algorithms, I'll
| often design a recursive version first, prove it correct, and
| then translate it into an iterative version. The translation is
| frequently required to implement the algorithm in common
| programming languages, most of which have poor support for
| recursion.
|
| For an example, see
| https://github.com/tmoertel/practice/blob/master/dailycoding...
| Bootvis wrote:
| See: How to Get Better at Recursion
| tromp wrote:
| As long as we're making bad jokes, here's another:
|
| In order to get better at recursion, you must first understand
| recursion.
|
| In order to get understand recursion, you must first understand
| recursion.
|
| (yes, the lack of a base case makes the joke even worse:-)
| canjobear wrote:
| I took an advanced Scheme programming class in grad school and
| for a good two years afterwards my code was full of all kinds of
| fancy recursion, continuation-passing style, monads, etc. I got
| really good at it. It was a waste of time. Loops are fine.
| [deleted]
| lostmsu wrote:
| Related to the topic, a programming game with really hard
| recursion puzzles: http://robozzle.com
| chaabani wrote:
| I think creating a simple programming language that supports
| recursion is a good way to get better.
|
| I did so in one of my side projects that I have recently released
| as an iOS and macOS puzzle game named "Recursive" where recursion
| plays a central role and allows solving levels with very short
| programs [0].
|
| Also, I may be biased, but I think that players can improve their
| mastery of recursion using the game.
|
| If you'd like you can contact me and I will gladly send you a
| promo code (contact email at website).
|
| [0] https://www.kidori.com/games/recursive/
|
| (edited to fix typos)
___________________________________________________________________
(page generated 2021-03-07 23:02 UTC)