Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Thinking About Recursion

solipsys.co.uk

Post reply on HN
Print view View original

21–30 of 42 posts

Re: Thinking About Recursion

#21

Post by nsomani »

arh68 wrote: post #16

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, b…

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.

Re: Thinking About Recursion

#22

Post by iCodeSometime »

imglorp wrote: post #8
jmnicolas wrote: post #7

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…

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.

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

Re: Thinking About Recursion

#23

Post by pgtan »

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?

Re: Thinking About Recursion

#24

Post by tel »

mdonahoe wrote: post #2

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”

Heck, I still think of variables as boxes with labels.

Re: Thinking About Recursion

#25

Post by [deleted] »

arh68 wrote: post #16

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, b…

[deleted]

Re: Thinking About Recursion

#26

Post by giornogiovanna »

› It's important to realise that variables in mathematics and variables in programming have a lot in common, but they are not the same thing!

I think the stated "differences" are actually similarities with programming languages.

› In mathematics, sometimes a "variable" is a place-holder for a value one may choose arbitrarily from a collection, and which is then used in some process,

That pretty much perfectly describes a function parameter: for a formal correspondence, universal quantification corresponds to dependent function types.

› In fact, sometimes we find that there is no value satisfying the requirements we have placed on the variable, so in a sense it doesn't exist at all!

That's what happens when your variable's type turns out to be uninhabited, like an empty enum.

› It seems to me, speculating idly and with no research to back me up, that recursion has similar conceptual challenges as Mathematical Induction and Proof By Contradiction.

The author used proof by contradiction as part of a proof that the well-ordering principle implies the principle of mathematical induction, but (1) that links recursion and proof by contradiction exactly as much as it links recursion and modus ponens, and (2) mathematical induction is usually taken to be the more fundamental rule anyway, so this bit doesn't make much sense to me.

› In mathematics a function doesn't even need to have a rule to tell you what it is,

It depends on your definition of a function. ;)

Related: the author lists rules such as "A finite path from an instance back to one of the simplest", which are formalized in the concept of a well-founded relation.

Re: Thinking About Recursion

#28

Post by skybrian »

Recently I was reading about digital signal processing and the difference between finite and infinite response filters.

Although probably not the way to teach it, it seems like there's a close relationship? A FIR filter is matrix multiplication on delayed inputs with a limited amount of delay, while infinite response filters use feedback in a way that seems similar to memoization of a recursive function on all previous inputs.

Re: Thinking About Recursion

#29

Post by redis_mlc »

ketzo wrote: post #10

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 be…

One of my favorite ways to think about recursion is that it's a shitty technique that can and will blow up your stack.

When I try to solve a problem with recursion, then I have two problems.

It's also a great way to filter out morons in interviews. If they ask for a recursive solution, and I tell them that it's a shitty solution, and if they don't immediately agree, then I know I'll be working with morons.

Re: Thinking About Recursion

#30

Post by rlpb »

ketzo wrote: post #10

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 be…

The challenge is to decide on the specification of what your function inputs and what it outputs. Get specification right, implement it as you describe (ignoring the task of your recursion goblins), and it'll work. Get the specification wrong, and the implementation will either be difficult or impossible.

It is helpful, of course, if someone else has defined a workable specification for you already.

Post reply on HN