3 ms·
I disagree somewhat, but I don't have time to write a detailed answer. Instead here's a quick sketch that is likely only intelligible if you have a fair bit of
by noelwelsh 10y ago
I disagree somewhat, but I don't have time to write a detailed answer. Instead here's a quick sketch that is likely only intelligible if you have a fair bit of PLT background.
The basic point is this: you don't need to teach "raw" recursion, just like you don't teach control-flow using goto. Just like structured programming introduced for/while/do loops to structure control flow, you can structure recursive programs into a few major groups. The most important one is good old structural recursion over algebraic data types. It's follows a very set formula, so there isn't much opportunity to go wrong. It helps to have pattern matching in your language to do this.
This is the approach taken by How to Design Programs (http://htdp.org/ http://htdp.org/)
Example blog post you might read if you want to know more about the theoretical background: http://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/ http://blog.sumtypeofway.com/an-introduction-to-recursion-sc...
- FeepingCreature 10y agoI think this depends on whether you're teaching down or up. I suspect both work for different people. (Down == "here's some abstract concept, here's some code that implements it in the language's abstract model", Up == "Okay so everytime you call a function, a new stackframe is created." That's the approach I personally prefer.) I think the reason why recursion is so hard to understand is that programming languages are incredibly misleading. You see "int a = 5;" and you assume that there's a unique 'a' to which 5 has just been assigned, which is of course a complete lie; 'a' is a template for a memory location which is defined only when the function is called. If you don't know this, recursion makes zero sense. "What, now there's two a's??" I should go do a blogpost on this.
- noelwelsh 10y agoI think trying to reason about recursion in terms of stack frames is madness. I find it quickly overwhelms my working memory. This is why we have the patterns---so you don't have to reason on the machine level. It's similar[1] to proof by induction, on the off chance that helps. [1] By similar I mean exactly the same as.
- FeepingCreature 10y agoI think reasoning about recursion in terms of stackframes is silly. But stackframes are useful for getting a handle on how recursion functions at all.
- noelwelsh 10y agoAh, I see. Agreed with that.
- qwertyuiop924 10y agoWell, no. Reasoning about stackframes, or even about recursive calls at a higher level, is how I understand a lot about recursion. It's also the only way to reason about whether a function will build up stack frames.