14 ms·
How the right syntax can help teach recursion
- MayeulC 10y agoThis is pretty interesting, and I am tempted to introduce this syntax in my next C programs. Would anyone advise against it?
- myst 10y agoWhy would any non-retarded person need any help getting recursion? Recursion is not hard.
- rosstex 10y agoYou'd be an excellent teacher!
- myst 10y agoThanks!
- exDM69 10y agoIt's not hard, but I the issue is a stupid way of teaching procedural programming in the first place, not a student with mental difficulties. When you've been taught that computers process a sequence of operations (ie. statements, not actual instructions), from the top to the bottom, it's difficult to imagine "start from the beginning, but rename all variables and substitute some values". Recursion is a bit hard when you do it in assembler (need to explicitly work with the stack), but that's not the mental model we typically use in programming. Yet, it's often the model that the students encounter first. I really liked the SICP lectures from 1980s where the lecturer goes ahead and demonstrates recursion with evaluating expressions by writing them on a blackboard with chalk. It also demonstrates the space and time complexity of the evaluation. This is why I think that beginner programming lectures should be more focused on expressions than statements. More functional, less procedural.
- JadeNB 10y ago> I really liked the SICP lectures from 1980s where the lecturer goes ahead and demonstrates recursion with evaluating expressions by writing them on a blackboard with chalk. It also demonstrates the space and time complexity of the evaluation. I agree! The author does just this when demonstrating the difference between the naïve recursive implementation of `length`, and the tail-recursive one using an accumulator. I don't know if he or she did so with the student, but I thought it was a nice pedagogical touch in the post.
- duncanawoods 10y agoThe problems I see are mostly with the word. When you face a word you don't understand it can be a huge obstacle unrelated to the concept it represents. Its especially bad when the definition is given to you as code you barely understand performing either a trivial task in a weird way that would seem to be a simple for-loop or a more sophisticated task involving say trees that you struggle to grasp even without the $5 word hanging over it telling you that you don't understand something. Terms like self-reference are more intuitive.
- posterboy 10y agoWith mutual recursion, two functions calling each other, the self-reference is indirect and this word therefore not explicit. Would that be mutual reference, cross dependence? Does it really matter? In the functionals spirit, it would be enough to treat recursion as an unnamed lambda of the type "clever trick" :)
- duncanawoods 10y agoI think you said it yourself "indirect self-reference" - its self-describing and doesn't require much explanation. It lets you concentrate on showing why its useful rather than what it is. It leads naturally to discussions of scope of references in languages that don't make self-reference easy. One reason I think the word becomes confusing is that recursive functions typically also require introducing a recursive data-structures. It makes the teacher feel powerful introducing a special concept but the learner struggles with what feels like a category error - they were trying to understand a processing concept and now its also a property that can apply to static structures too.
- JadeNB 10y ago> Why would any non-retarded person need any help getting recursion? Recursion is not hard. As I think was implicit in rosstex (https://news.ycombinator.com/item?id=12504541 https://news.ycombinator.com/item?id=12504541 )'s comment, this attitude is worthless. Evidently recursion is not hard for you, but there are people who find it hard. If someone else has found an educational approach that works for at least one such person, then what is the use of sneering at it, without even offering anything constructive in return? A teacher who said such a thing would not only not help his or her students this time, but ensure that they'd never look for help in the future.
- posterboy 10y agoThat is a complicated case for teachers. Dumbed down content slows the progress of the more talented students and vice versa. The system is not perfect so the GP is entitled to his opinion, IMHO. Of course, "dumb" is a debatable characterization, but since the GP didn't start to debate it with actually concrete arguments, the point is moot and just a slur.
- JadeNB 10y ago> That is a complicated case for teachers. Dumbed down content slows the progress of the more talented students and vice versa. Your points are excellent and constructive. It is well stated that a classroom cannot always be serving the needs of each of its members, since they will sometimes be in conflict, and that part of the job of a teacher is to figure out how best to address these disparate needs. My objection was not to this constructive point, but rather to the dismissive ideas (not yours, of course) that (1) having difficulty with a concept (whatever that concept is!) is the mark of a mental disability rather than part of the learning process, and (2) it is worthless even to attempt to address and resolve this difficulty.
- ChoHag 10y agoThey might be 12.
- sctb 10y agoYou cannot post like this here. Please comment civilly and substantively on Hacker News—we ban accounts that don't do this. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- jbb555 10y agoThis just looks extra confusing to me
- yanickmartel 10y agoI think the best way to explain it is that a recursive function is a function which should return either: - A 'base case' value - The result of a call to itself (could be multiple calls to itself also) Basically when you call a recursive function, unless it hits the base case (usually decided by an if condition), it will keep calling itself (often with slightly different arguments each time) until it returns the base case. Once the function returns the base case, the recursion will start to 'unwind' - In the unwind phase, you can use the return values of the previous recursive calls to do more interesting stuff. The best way to visualize recursion is to imagine that you have a stack of function calls; each time a function calls itself, it creates a copy of itself with new arguments and puts that copy on top of the stack - Then the program pointer moves to the copy (but it keeps a reference of were it was in the previous call) - And it keeps building up the stack with new copies of the function until it reaches the base case (when the function finally returns a concrete value). The 'unwinding' phase is just when the functions start returning (after the base case has been reached) and all the function 'copies' just get popped off from the top of the stack one by one - Each time the program will continue running from wherever it was in each call stack.
- lhnz 10y agoExplaining recursion is a lot easier than writing recursive functions. I can actually describe explicitly why I've occasionally found writing a recursive function hard. In fact I expect a UI could be created that would make it much much easier. Basically, for ordinary functions I'm able to remember the values stored in each of the variables. (I do not mean a real computation, but the pretend computation I do at all times when programming.) However, with recursive functions, I sometimes find myself having to remember 5 or more levels of these same variables. Therefore if I have 5 variables, I might end up having to hold 25 values in my head; obviously it is less than this since often there is some pattern to the values that aids in remembering them. Additionally, I need to flow the return values back through the functions potentially performing extra computations on them; this can be extra confusing if there were multiple entry-points at a particular recursion level of a function. For example, what line and column number was the function called at, and which block of a function was it within? And, do these values belong to the 7th or 9th call of the function? Due to this I'm no longer able to rely on my memory, and I don't get the cognitive benefits of associating computations to place. Another issue is that if you write some code which never matches its 'base case' it never finishes computing. This is often difficult to debug, and it can cause your machine to lock up. Perhaps the solution might be: - A table to represent the values within a recursive function. With colour coded cells that show which level of function a value comes from (and whether it was an argument or return from a deeper level). Effectively, the idea is to reassociate computation with 'place'. Method of Loci. - Some tools in order to troubleshoot the times in which they've misprogrammed the 'base case'. For example, set a particular recursion depth when developing and exit if this gets reached. Visualise separately how values are advancing towards matching this 'base case'. I could probably come up with more, but I need to think concretely again to do so usefully; and I'd need to experiment with different recursive solutions to find out whether I'm solving their individual problems.
- noelwelsh 10y agoI 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.
- 10y ago
- d--b 10y agoWow, the guy really is teaching his students how to program using his side-project language?! Man, if I was the student, I would be pretty upset. There are plenty of popular programming languages to learn. Each one has its own caveats. It's hard enough to learn CaML, or C, or Lisp, but these are at least used in the world! Why would the student need to learn a programming language that no-one uses? It's either that the teacher is using them as guinea pigs, which is bad enough, or using them advertisement, which is even worse. All in all, he's certainly not making them a favor!
- leephillips 10y agoWas Knuth wrong to make up a language to use in his Art of Computer Programming books?
- JoeAltmaier 10y ago...or teaching them facility in learning a language, which is more valuable than knowing any particular language.
- dspillett 10y ago> Why would the student need to learn a programming language that no-one uses? The same reasons many examples in textbooks and documentation are in pseudo-code. Sometimes you want to learn general concepts and don't want implementation oddities of specific language(s). Theory first then practice. That way you are more likely to end up with a skillset you can easily transfer between languages/frameworks/platforms/other. Essentially his language is the same as any other "made up" pseudo-code syntax.
- eutectic 10y agoI think the best way to understand recursion is in terms of induction. If someone gave you the solution to your problem for different inputs, could you compose them together to solve the problem for your current input? Then you just have to show termination. Thinking procedurally (i.e. in terms of 'unfolding' the call stack) is unlikely to provide much insight.
- shiro 10y agoQuoting the author: With Lisp it's always been non-trivial to know when a function is tail-recursive. You can't just blindly count parens, you have to try to "run" the function in your mind. To me, Lisp code is just like a tree (well, sometimes DG) and it's statically obvious where the leaves are---no need to "run" the function in mind. But maybe it's just because I get used to it; once you learned, you forget what you saw (or you didn't see) before.
- qwertyuiop924 10y agoIt's actually not hard to see if a Scheme function is tail-recursive, for another reason: All Scheme functions are tail recursive. The difference is whether you're building up stack frames by calling a recursive function inside that last form in the function, thus requiring the language to build an extra stack frame for it. The only difficulty in seeing if a function is tail recursive, either way, is just checking for branch instructions. This becomes easier if you wait until the thing's been macroexpanded, and have the lexical environment available so you can tell what names refer to what. Again, Schemes need not bother with this: when you comes across the expression will be the return value, tail-call the outermost function, after collecting the values of all inner functions.
- taeric 10y agoI feel that you are working with a different version of "tail recursive" than any I have heard before. Specifically, it is certainly possible to make a non-tail recursive implementation of fib in Scheme. Curious why you seem to be implying otherwise.
- qwertyuiop924 10y agoI was talking about the mechanics of the compiler/interpreter, at least the original Sussman/Steele implementation. Let's look at Factorial in Scheme. You mentioned Fib, but Factorial is a simpler example, and will suffice. (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) The Scheme compiler/interpreter will detect that the last expression to be evaluated, and thus the return value will be: (* n (fact (- n 1))) Now, you might think that Scheme would detect this as ineligible for TCO, but that's not what happens. In fact, what happens (in pseudo-asm) is this: push *n push $1 call subtract ;;returns t1 on the stack, taken as arg by fact call fact ;;both n, and t1, the args to mult, are on the stack, followed by the return address. jmp mult ;;mult re-uses the stack frame, so it's a tail call. obviously, in a real asm, sub and mul are primitives, not funcalls, but you get the idea. If that didn't make sense, just read, "LAMBDA: The Ultimate Declarative." it explains it better than I could. So yes, all functions in Scheme are TCOed (at least, in the original implementation), it's just that some of the build of stack frames. I don't know if that's how other languages work, but it might be.
- dschiptsov 10y agoAnything better than Haskell's?
- qwertyuiop924 10y agoFunnily enough, that Lisp, guaranteed not to run anywhere in this universe, is almost valid Scheme, under SRFI-49 or Wisp. The only thing you'd have change is change def to define, and replace rest.x with (cdr x).
- 6DM 10y agoI feel like it would be easier to walk through how the machine deals with it at an assembly level. I if you restrict to a really basic level of just pushing, jumping, and linear execution. Recursion then just becomes executing instructions, even if it means calling the same method you're already executing in.
- bmm6o 10y agoIt is a little interesting that it takes so few changes to the source to rewrite the recursive call as a loop. But really the only advantage it has over C (syntactically, anyway) is that it doesn't require a return at the end. By which I mean, it's kind of a stretch to call this the "right" syntax.
- sn9 10y agoJust throw The Little Schemer at them.