Re:How the right syntax can help teach recursion
by FeepingCreature on Thursday September 15, 2016 @07:03AM
(#12504945)
I 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.
Re:How the right syntax can help teach recursion
by noelwelsh on Thursday September 15, 2016 @07:10AM
(#12504981)
I 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.
Re:How the right syntax can help teach recursion
by qwertyuiop924 on Thursday September 15, 2016 @10:49AM
(#12506600)
Well, 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.
Re:How the right syntax can help teach recursion
by FeepingCreature on Thursday September 15, 2016 @07:36AM
(#12505142)
I think reasoning about recursion in terms of stackframes is silly. But stackframes are useful for getting a handle on how recursion functions at all.
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/)
Example blog post you might read if you want to know more about the theoretical background: http://blog.sumtypeofway.com/an-introduction-to-recursion-sc...