Understanding Recursion as an Absolute Beginner • Hacker News Board

Re: Understanding Recursion as an Absolute Beginner

#51

Post by DonaldPShimoda » Fri, Sep 06, 2019, 3:20 PM UTC

lhnz wrote: post #28

When I was a beginner the two problems I had with recursion were: 1. Not handling the base case and accidentally causing an infinite loop. 2. Never reaching the base case so ending up in an infiniite loop. 3. Creating too much incorrect state, and not having a sane way of debugging or visualising this due to the speed and quantity in which it is created. Nowadays, I carefully focus on the first two problems, before m…

The way I explain implementing recursion is this:

1. Write down what your function does in a comment. (e.g., "sum all the elements of a binary tree"). 2. Write the function signature. 3. Write the base case. (This is usually straightforward and most people don't seem to have an issue with it when reminded.) 4. Stop thinking. 5. Assume your function already works and write the recursive case. 6. Profit!

I find where most people get confused over recursion is in trying to reason about the recursive case. They think "Well if I start at the root of the tree, then the next thing I need is to get the children... and then... with the first child... uh..."

They get lost in the recursion. So I tell them: assume your function already works. Trust that you will write it correctly eventually. What does your function do? How can you use that?

If you assume you already have a function that sums binary trees, and if you're trying to sum the children of a branch node, well then use that function that you already have to get the sum of each of those children trees, and add up the results!

I always recommend to never try to visualize N levels of recursion, unless you're working through an example to actually test your implementation. Worrying about the deeper recursion is how people get lost and confused. Keep it simple: just look at the one layer and assume the other layers will do their job correctly.

Re: Understanding Recursion as an Absolute Beginner

#52

Post by joelfolksy » Fri, Sep 06, 2019, 5:21 PM UTC

alejohausner wrote: post #36

The problem with recursion (and with the counting example in the post) is that a student will ask "why can't I do this with a loop?" It's better to use a problem where recursion MUST be used, such as a binary tree: The size (# of nodes) of a binary tree is: - 0, if the tree is empty, or - size of left subtree + size of right subtree + 1 If you draw a tree, any student will agree that the recursive method makes sense.…

The natural solution would be to teach it before loops, yes?

Re: Understanding Recursion as an Absolute Beginner

#53

Post by diminoten » Fri, Sep 06, 2019, 8:27 PM UTC

DonaldPShimoda wrote: post #48

diminoten wrote: post #3

How "absolute beginner" are we talking here? At what point have we distilled a concept to its bare minimum and failure to understand simply requires the person to spend more time with the concept? If recursion is difficult to grasp, I'm afraid it's not going to get any easier from there.

> If recursion is difficult to grasp, I'm afraid it's not going to get any easier from there. I strongly disagree. Many people have never had to reason about recursion so explicitly before going into CS. Just because it's difficult to understand explicitly at first doesn't mean they won't get better. If they never understand recursion, then that's a problem, but I think that probably says more about the teacher than…

What do you strongly disagree with, exactly?

Re: Understanding Recursion as an Absolute Beginner

#54

Post by ErotemeObelus » Sat, Sep 07, 2019, 7:03 AM UTC

RcouF1uZ4gsC wrote: post #9

>Most of the people find recursion difficult but it's not. Recursion is really hard. According to https://phys.org/news/2019-08-recursive-language-modern-simu... Recursive language is a relatively recent phenomenon and even now is much harder to acquire than language and grammar. Recursion is probably the biggest thing that separates our communication from that of other species and gives such a big advantage. That be…

Any primitive recursive algorithm can be trivially transformed into a series of for loops and a stack object. Any recursive algorithm can be trivially translated into a series of white loops and a stack object.

An exercise for people who don't understand recursion: get recursive algorithms from a book and use your built in Python or whatever stack class and make them into for loops in a cookie-cutter way.

This is making a myth about the Big Conceptual Leap from small for loops into Big Recursion. It is literally impossible to not do recursion if you understand for loops. At the very worst, you can write it out in for loops first and then translate it piece-by-piece.

Re: Understanding Recursion as an Absolute Beginner

#55

Post by arc33 » Mon, Sep 09, 2019, 3:23 PM UTC

DonaldPShimoda wrote: post #47

arc33 wrote: post #16

I think the simplest way to understand recursion is as a for loop where you use the stack as the counter. Recursion is basically implementing the operations of a repetitive loop but the loop controls are not explicit like in a for loop, instead you use the stack as the counter of the loop. Once you think of recursion as just another way to do for loops, it immediately is demystified.

> Once you think of recursion as just another way to do for loops, it immediately is demystified. I actually think this is not a good way to understand recursion. It's like saying "once you think of the lambda calculus as another way to build a Turing machine, it immediately is demystified." Yes, it's true that they're equally powerful, but their differences are what make one or the other more suitable to certain cir…

> but they don't really mean anything in relation to the program: they're just a procedure to get the job done.

Actually, I don't think till now I've got recursion. I only see it used in bunch of places and I've understood it enough to see how it works. Not quite sure, how it should click for me?