[HN Gopher] Thinking About Recursion
___________________________________________________________________
Thinking About Recursion
Author : ColinWright
Score : 56 points
Date : 2020-02-09 08:10 UTC (1 days ago)
(HTM) web link (www.solipsys.co.uk)
(TXT) w3m dump (www.solipsys.co.uk)
| gota wrote:
| Prolog _really_ helps with learning recursion. Much easier to
| learn the core concepts in a declarative way than in a procedural
| way
| mettamage wrote:
| IMO my favorite way to think about recursion is to build up a
| call stack and then draw the return arrows.
| jmnicolas wrote:
| I always thought recursion was very elegant, but until now I was
| using it to scan through folders on the file-system and that was
| about it.
|
| Then I had an interesting problem at work where recursion seemed
| the most elegant solution ... but I quickly encountered errors
| that were not caught in a try catch block and made the program
| fail silently.
|
| I'll admit my ignorance, but I thought a stackoverflow was a
| "feature" of low level programming languages such as C and C++
| since I never encountered one in 10 years of coding in C#.
|
| So it seems my love for recursion will have to remain mostly
| platonic and I'll have to use those unappealing loops for a
| while.
| imglorp wrote:
| If you're getting a stack overflow, you might check if your
| language supports tail call optimization, or just known as tail
| recursion. Not all environments support this, but if you can
| rearrange your recursive function it would avoid the overflow.
|
| The short version of the tail call story is only one copy of
| the stack frame is kept, instead of all of the frames on the
| way down.
| iCodeSometime wrote:
| Alternatively, adding some kind of memoization can reduce run
| time and stack size pretty significantly for some algorithms.
|
| e.g. if you're using recursion to compute fibonacci, you're
| re-computing quite a lot of steps by default
| gliese1337 wrote:
| You really need language support to make recursion the best
| practical solution for most problems. However, even when
| working in "normal" languages like C#, I find that recursion
| has utility in designing solutions--it is often easiest to find
| a provably-correct solution for an inherently recursive problem
| by actually designing a recursive algorithm; you merely then
| have to perform some compiler work yourself to transform that
| initial design into an efficient iterative implementation.
| herbstein wrote:
| In some cases in C# you can write a tail-recursive function
| and then have Resharper rewrite it into a loop for you.
| pgtan wrote:
| I tried to explain recursion to my son with the monks from
| "Towers of Hanoi": What is a monk handing out to the next one? Is
| he waiting? What is a monk's contribution to the answer? How many
| monks do we need? What does the last monk do? Which monk gives
| the answer, the first one or the last one?
| mdonahoe wrote:
| I like thinking about variables as boxes with labels. Hadn't
| heard that before, but seems like a simple way to teach people.
|
| I skimmed the description of recursion. Seemed a bit long for my
| taste.
|
| I was taught how to write a recursive function like this:
|
| "Write the function signature, the docstring, and the base case.
| Then assume the function already works, and use it to implement
| the rest of the code"
| mettamage wrote:
| It's how I teach people. I also think of variables as boxes and
| labels. Tje caveat is that for a non-primitive datatype, I put
| the address of a vault in the box and will go to the vault,
| everytime I use the value of the variable.
|
| I'm not talking pointers here, simply references.
| freetonik wrote:
| I do a similar thing but with functions: running functions are
| boxes with labels, function definitions are blueprints of
| boxes. I use it in videos [1] to explain recursion.
|
| 1. https://youtu.be/vLhHyGTkjCs
| choeger wrote:
| When you write recursive functions like this, you should keep
| in mind to get strictly closer to your base case with each
| recursive step (for some feasible definition of "closer"),
| otherwise you might never reach that base case.
| buildawesome wrote:
| I find it hilarious that solipsys is writing about recursion.
| bugmen0t wrote:
| To think about recursion, you first have to think about
| recursion.
| goatforce5 wrote:
| Try starting here:
| https://news.ycombinator.com/item?id=22292086
| DesiLurker wrote:
| > Thinking About Recursion
| arh68 wrote:
| This was how I was "taught" recursion, with (Lucas) Towers of
| Hanoi. Ugh! I still remember the mostly-filled in function with
| 2(?) recursive calls placed, for us to fill in the arguments.
| _How the heck would that ever work?_ was all I could think. I don
| 't think a single person in the class had any idea of progress
| until the teacher, kinda exasperated, just _told_ us. And we
| still didn 't get it, of course. I get it now, but only from a
| more task-oriented mindset, not Java Mad Libs.
|
| The only recursion that still bothers me is Clownsort / Stooge
| sort [0]. That such an algorithm would work is still not my gut
| feeling.
|
| [0] https://en.wikipedia.org/wiki/Stooge_sort
| nsomani wrote:
| I think the intuition behind your Stooge sort example is that
| for an array separated into three segments:
|
| A | B | C
|
| The first sort moves the largest elements of A and B into B.
| The second sort moves the largest elements of B and C (and
| therefore of A, B, and C) into C. And the final sort properly
| orders the elements within A and B.
| ketzo wrote:
| One of my favorite ways of thinking about recursion (and proofs
| by induction) is the recursion goblins.
|
| When you're writing a recursive function, you don't worry about
| how you _got_ your input. The recursion goblins took care of
| that.
|
| You also don't need to worry about what will happen to the thing
| that you _return_. The recursion goblins will take care of that,
| too.
|
| All you need to worry about is what's happening in between the
| curly brackets, which is that you should make your problem _a
| little smaller_. The recursion goblins will take care of the
| rest.
|
| This was weirdly freeing for me in CS 101/102/103 etc.; I was
| getting way too wrapped up in trying to visualize the recursion
| from start to finish, and that's a crapshoot at the best of
| times, even if it's sometimes important. Much more often, though,
| you can get a lot done a lot faster if you trust the goblins!
|
| (Thanks to Professors Shindler and Cote for this one)
| [deleted]
| hinkley wrote:
| Working a problem from bottom-up flushes out a lot of the
| incidental information, making the problem much easier to
| comprehend. By using the goblin analogy you're focused on the
| _last_ call, and working back from there.
|
| The Refactoring people knew this, and the Mikado method is
| essentially a way to find the 'bottom' when all you can see is
| the top of the rabbit hole, so you can use these other skills.
| [deleted]
___________________________________________________________________
(page generated 2020-02-10 23:00 UTC)