Embedded recursion is much harder than tail recursion. This reminds me of the difficulty of central embedding vs tail embedding in linguistics.
Level 3: tail recursion program (:SIDE = 80)
TO SHAPEB :SIDE
IF :SIDE = 20 STOP
REPEAT 4 [FORWARD :SIDE RIGHT 90]
RIGHT 90 FORWARD :SIDE LEFT 90
SHAPEB :SIDE/2
END
Level 4: embedded recursion program (:SIDE = 80)
TO SHAPEC :SIDE
IF :SIDE = 10 STOP
SHAPEC :SIDE/2
REPEAT 4 [FORWARD :SIDE RIGHT 90]
RIGHT 90 FORWARD :SIDE LEFT 90
END
> Mental model of embedded recursion as looping - The children were fundamentally misled by thinking of recursion as looping. While this mental model is adequate for active tail recursion, it will not do for embedded recursion.
> programming constructs often do not allow mapping between meanings of natural language terms and programming language uses of those terms. Neither STOP or END stop or end, but pass control back. The reason that this is important for the Logo novice is that when their mental model of recursion as looping fails, they have no way of inferring from the syntax of recursion in Logo how flow of control does work. So they keep their inadequate looping theory, based on their successful experience with it for tail recursion, or blame discrepancies between their predictions and the program's outcomes on mysterious entities such as numbers, or the "demon" inside the language itself.
> Beyond mistaken mental models about recursion, we have found these to involve atomistic thinking about how programs work, assigning intentionality and negotiability of meaning as in the case of human conversations to lines of programming code, and application of natural language semantics to programming commands.
It seems the children's model is BASIC-like in that a function call is just equivalent to "GOTO <#LINE>", and that the program state is just the line number currently being executed.
The part that is missing is the stack. So I wonder what would happen if you let them step through while showing the stack state at every point. This would clue them in immediately that there is nested control flow.
The part about alternative explanations is funny but just reflects the fact that there is an element of the language not reflected in the code, that they can't just reify visually (unlike the instruction counter).
That is, the kid who inferred that there was an invisible "demon"... was right.
It seems the children's model is BASIC-like in that a function call is just equivalent to "GOTO <#LINE>"
>The part that is missing is the stack.
Bingo. Function-call-as-GOTO and not knowing about the stack are the root cause of so many confused questions on beginner programming forums. You can spot it a mile away because they tend to write functions without any parameters or return values. Instead, they pass information around by mutating global state everywhere. It's difficult to fit the idea of parameters and return values into a mental world that doesn't include a call stack, so their absence in novice code isn't surprising.
A friend in college (Aerospace major) took an intro to programming course in C, and was calling main() to get back to the menu at the start of his program instead of using any sort of loop. Was so confused why he had to choose "quit" from the menu a whole bunch of times before it would actually exit.
>Why is this important? As I read the book (and if you read my notes, you know where this is going) I started to notice something in the wording and tone. The further I progressed the more I became convinced of it, and I think it explains how he managed to mangle the explanation of C pointers so badly.
>I don’t think he understands the call stack.
[...]
>Suppose you’re used to writing BASIC for small memory electronic devices and you learn about C. You read about pointers and realize something: it’s possible to write a subroutine that can change variables without knowing their names. It’s manna from heaven! You don’t have to devote global variables to being the “parameters” of your subroutines anymore. Life is great.
>This is the mindset I think Traister had and never got past.
> The part that is missing is the stack. So I wonder what would happen if you let them step through while showing the stack state at every point. This would clue them in immediately that there is nested control flow.
I saw so many of my peers needlessly confused by a pedagogy that insists that the call stack is an implementation detail and thus does not belong in a CS class.
Nitpick: the call stack is an implementation detail. It is a way to implement call frames.
Because that implementation doesn’t handle functions returning closures that depend on the call frame, something that is very common in modern languages, I think we should teach call frames first.
Starting with a call stack makes understanding how closures work later unnecessarily hard.
> Nitpick: the call stack is an implementation detail. It is a way to implement call frames.
Sorry, I was unclear that it was the second half of the implication I disagreed with. I never had the pleasure of a SICP based class, but I did eventually learn the concept of closures (though never in a CS class). Many of my peers were flummoxed by recursion and I personally believe that intentionally avoiding discussion of a call stack was poor pedagogy (possibly because I leaned on my understanding of it when I first learned recursion) that unnecessarily caused people to drop out long before they would ever encounter closures.
> Because that implementation doesn’t handle functions returning closures that depend on the call frame, something that is very common in modern languages, I think we should teach call frames first.
I guess I'm showing my age. Pascal, C, C++ and Java (which at the time lacked not only closures, but also generics) were the only languages I encountered in my CS classes (there was an optional upper-level survey of languages class that I didn't take). I will, however, stand by my general sentiment that there are a large class of people that learn better by learning a concrete example and then generalize to the abstract, and those students were poorly served by the pedagogy I encountered.
Our version of Logo has both a step execution mode and a way to follow execution in the editor, but I admit there currently isn't a built-in way of showing how far down the recursion rabbit hole an execution path has gone (I've put it in the backlog)
Debuggers, though "one more thing to think about" whilst learning do actually make things easier to understand for a beginner.
I try not to introduce them too early because lots of concepts at once gets frustrating - but eventually you get to a point where it clearly would save stress to be able to step and inspect state.
Oh, right, I forgot to mention what the children are in this study.
> Seven children (two girls and five boys, eleven- to twelve-years-old) in their second year of Logo programming participated in the study. The children were highly motivated to learn Logo programming, and had averaged over fifty hours of classroom programming time under the supervision of experienced classroom teachers knowledgeable in the Logo language, who followed the "discovery" logo pedagogy set out by Papert [3]. All seven children had received instruction in iteration and recursion, and had demonstrated in their classroom programming that they could use iteration and recursion in some contexts
To those who don't get what "discovery" method implies, it is proposed by Seymour Papert, a pioneer of computer pedagogy, based on the constructionist theory of learning. It posits that students learn best when they are actively engaged in constructing their own knowledge and understanding through the creation of personally meaningful artifacts or projects. They would be on their own, writing programs with minimal guidance, developing their own intuitive understanding of how programs operate.
I don't know what was Papert's intention, as I never read his book Mindstorms in full, but from what I read, I think 20% probability he believed that the "stack" concept would be discovered by children, and 80% probability he believed that children should be allowed to discover concepts on their own, even if they "misunderstand" the nature of computer programming, because there is no nature, except what we construct of them, and so there is nothing to "misunderstand". He is a radical constructivist in pedagogy.
Notably, in the study, the children were receiving instructions (though what kind of instruction, the authors didn't say). It was discovered that pure discovery learning is extremely inefficient, and so most actual discovery learning programs were not "pure", but included extensive instruction, or guidance. See for example Mayer, R. E. (2004). Should There Be a Three-Strikes Rule Against Pure Discovery Learning? American Psychologist, 59(1), 14–19.
I actually was thinking of adding this study somewhere in my post on the Perceptron Controversy, but don't have a good place to place it.
> Embedded recursion is much harder than tail recursion.
Tail-end recursion is just a way to express a loop. Yes, true recursion is much harder to get your head around than a loop. The fact that the loop is expressed as tail-end recursion doesn't change the basic fact that loops=easy, recursion=headache.
I mean it's a non-obvious-to-me interesting finding though that people understood "loop expressed as tail-end recursion" as easily loop expressed as loop though! Like it's not obvious to me that their semantic equivalence would be obvious to a beginner!
I don't remember finding tail-recursion easier to learn than embedded recursion -- I do recall it being very confusing for me to learn at first either way, but I can't recall exactly what was in my head then, or how it was taught to me! It was a long time ago. But I remember finding it tough to understand.
I think recursion in the tail position makes sense because "you have to go somewhere", it is just another place to go. Recursion in the middle is like starting over, so they might think of it as a weird jump.
I'd love to teach kids to program, so many minds to run (ethical) metacognitive experiments on! Once you understand recursion, you never go back (and with tail recursion you don't have to). :)
It’s not clear whether these results would generalize much beyond Logo. Reading the part which starts with “To understand how recursive procedures work in Logo one must know:” makes Logo recursive procedures sound pretty terrible - typical ad-hoc language design.
> this acts to insert all lines of the named procedure into the executing program at the point where the call occurred
...is quite dubious, perhaps it works in Logo, but in many languages it would raise scoping issues at the very least. Procedures calls are not in general the equivalent of textually cutting and pasting the procedure's code. Given that Logo has dynamic scoping, perhaps it works - but that's an issue in itself, dynamic scoping is hard to reason about in general.
Aside from the dynamic scope issue I mentioned (which someone else has expanded on), this doesn't work for languages that support closures. "Fully qualifying" names doesn't help there. And OO languages would have similar issues for much the same reason.
Most programming languages today don't have dynamic scoping. Here's something you could do in a language that had it.
print_x() {
print(x);
}
foo(msg) {
let x = msg;
print_x();
}
main() {
let x = "Hello!";
print_x();
foo("Goodbye!");
print_x();
}
In a language with dynamic scoping, this would print:
Hello!
Goodbye!
Hello!
With lexical scoping, most dynamically scoped code would either be a compilation error, or it wouldn't work. In this case, the language would complain that x wasn't defined in the scope of "print_x()". With lexical scope, you'd have to make x a global variable, and then the function foo() would just be equivalent to calling print_x().
... or simply that the LOGO language syntax and choice of commands is confusing? Without formal explanation, how surprising is it really that a child would assume that STOP mean stop?
I'd bet that if LOGO had used RETURN, like many other languages, then the children's reasoning would be likely be more accurate. Or go the other way and make them tell you what this or that brainfuck[1] program does. So, to me, this research says more about LOGO choices than anything.
But STOP does mean stop. Stop executing this subroutine.
If the program were instead (as a set of commands for a person, not a turtle) START WALKING; STOP; START CLAPPING; STOP; ... any child would understand what was intended. It would be more confusing if the first STOP here meant "stop all program execution, never proceed to the next step".
So the problem isn't STOP, it's the fact that there's more program to execute, hidden in the call stack.
This paper also appears in the 1989 book Studying the Novice Programmer (edited by Soloway and Spohrer). When I was looking into programming education research in the '00s this was still being suggested as a source for important experimental results, does anyone have a recommendation for a modern survey or textbook?
Embedded recursion is much harder than tail recursion. This reminds me of the difficulty of central embedding vs tail embedding in linguistics.
Level 3: tail recursion program (:SIDE = 80) TO SHAPEB :SIDE IF :SIDE = 20 STOP REPEAT 4 [FORWARD :SIDE RIGHT 90] RIGHT 90 FORWARD :SIDE LEFT 90 SHAPEB :SIDE/2 END Level 4: embedded recursion program (:SIDE = 80) TO SHAPEC :SIDE IF :SIDE = 10 STOP SHAPEC :SIDE/2 REPEAT 4 [FORWARD :SIDE RIGHT 90] RIGHT 90 FORWARD :SIDE LEFT 90 END
> Mental model of embedded recursion as looping - The children were fundamentally misled by thinking of recursion as looping. While this mental model is adequate for active tail recursion, it will not do for embedded recursion.
> programming constructs often do not allow mapping between meanings of natural language terms and programming language uses of those terms. Neither STOP or END stop or end, but pass control back. The reason that this is important for the Logo novice is that when their mental model of recursion as looping fails, they have no way of inferring from the syntax of recursion in Logo how flow of control does work. So they keep their inadequate looping theory, based on their successful experience with it for tail recursion, or blame discrepancies between their predictions and the program's outcomes on mysterious entities such as numbers, or the "demon" inside the language itself.
> Beyond mistaken mental models about recursion, we have found these to involve atomistic thinking about how programs work, assigning intentionality and negotiability of meaning as in the case of human conversations to lines of programming code, and application of natural language semantics to programming commands.