8 ms·
Thinking About Recursion
- guiambros 10y agoMandatory xkcd-clone: http://thomaspark.co/2017/01/relevant-xkcd/ http://thomaspark.co/2017/01/relevant-xkcd/ Previous discussion: https://news.ycombinator.com/item?id=13793404 https://news.ycombinator.com/item?id=13793404
- jonsen 10y ago"Let me see if I got this recursive disk juggling right. You move the top-most disk to position C. Then recursion can move the rest to position B. And finally I move the disk at position C on top of the rest at position B." "No, no, no. Look ..." "But to start you can only move the top-most disk?" "Yes, but it won't work because ..." "What? You have to move the top-most as the first move."
- kjhughes 10y agohttps://news.ycombinator.com/item?id=13819624 https://news.ycombinator.com/item?id=13819624
- jsperson 10y agoI just spent an hour reading this blog. I now feel absolutely smarter and relatively dumber. What a wonderful blog. Thanks for sharing!
- ColinWright 10y agoWow. Thank you.
- akkartik 10y agoI feel fairly confident that I've solved the problems of teaching functions (http://akkartik.name/post/mu http://akkartik.name/post/mu ; particularly the last couple of sections) and recursion (http://akkartik.name/post/swamp http://akkartik.name/post/swamp). Tl;dr - It just requires first introducing these ideas in a statement-oriented language without recursive expressions. Allow learners to see the steps unfold explicitly, one by one. (Comment deliberately phrased provocatively to hear push-back and feedback.)
- ihoz 10y agohttps://www.google.com/search?q=recursion https://www.google.com/search?q=recursion
- Koshkin 10y agoTo those who might be under the impression that recursion is not all that useful in the practice of commercial software development (as opposed to a purely academic interest or as a method of solving logical puzzles) I would point out the fact that recursion is the only way to emulate iteration in functional languages and, as such, it finds extensive use in the C++ template language as well as XSLT - two most used pure functional programming languages today.
- brianberns 10y agoMany commonly-used data structures (e.g. trees) are nearly impossible to manage without recursion.
- crimsonalucard 10y agoNot true. A loop and a stack can achieve the same thing!
- ihoz 10y agoRecursion is nothing more than implicitly using a stack (via the call stack) or explicitly with a loop. You just won't get a stack overflow exception with the loop -- you'll run out of heap instead. It's still the stack filling up.
- vertex-four 10y agoIndeed. People who claim recursion is the only way to handle some types of data structures are missing how recursion is implemented. In practice, it boils down to a stack and a loop - and in the case of tail-recursive functions, not even the stack - though it may be a little prettier if you use recursion.
- charles-salvia 10y agoRecursion sometimes makes it easier to implement certain algorithms, since modern programming languages have an implicit call stack which conveniently provides a snapshot of the state of all local stack variables at that point in the algorithm.
- yazaddaruvala 10y agoKinda off topic. And a kinda crazy hypothetical: I would really like to see a production language, where program-stack based recursion was a compile time error. Instead, only recursion as syntax sugar is allowed. i.e. Only recursion (or any cyclic function call graph) that the compiler can translate to "imperative code", should be allowed to compile. For two reasons: 1. I honestly dream of a world where we can no longer think about infinitely propagating program-stacks. 2. It would force us to invent better optimization algorithms (like tail-call optimization) but for more general recursive patterns.
- buzzybee 10y agoOh, I do believe this was attempted with Algol 60. And there's an article on what happened. It turns out to be (possibly mathematically) unfeasible as there are many ways to sneak it in. [0] https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664
- crimsonalucard 10y agoI'm sure it can be done. The compiler just needs to manually create a stack as a variable rather than use the call stack.
- colorint 10y agoYou also need the iterative structure to support continuations. Of course, if you do all that---you've just reimplemented function calls.
- dreamcompiler 10y agoYou're talking about continuation-passing style, which makes stacks superfluous. It's a mind-blowing idea. But it's also a royal pain to write code directly this way, so some compilers convert to continuations under the sheets.
- yazaddaruvala 10y agoIts crazy that this idea was invented in 1975[0], and I haven't heard of it, even after: - 4 years of self learned programming - 4 years of university for computer engineering - 5 years in the industry, as a software engineer [0] https://en.wikipedia.org/wiki/Continuation-passing_style https://en.wikipedia.org/wiki/Continuation-passing_style
- deleted 10y ago[deleted]
- brianberns 10y agoMan, this article really shows why imperative programming is so much harder to reason about than functional programming. Difference between "variables" in math vs. functional programming? None. The value of a variable can't change. Difference between "function" in math vs. functional programming? None. It's just a map from one set to another.
- dualogy 10y agoIncomplete assessment. Functional programming much better supports equational reasoning. Imperative programming much better supports operational reasoning. Or you could contrast "data flow" vs "control flow". I'd have thought we won't need operational reasoning in 2017 but currently I conclude it may always be a part of computer programming..
- komali2 10y agoI don't really know much about functional programming. How can a variable not change?
- dualogy 10y agoConstruct a whole program of functions only with say `readonly` (in c#) or `const` (in EcmaScript) or only `:=` (in Go) "variable" "assignment-declarations", never mutating them after initial declaration. It's possible and it's one of the core tenets of purely FP.
- crimsonalucard 10y agoIn functional programming the entire program is literally a single expression. This is essentially what functional programming is. A variable in a single expression cannot be modified.
- clusmore 10y agoIn mathematics, variables don't change inside expressions -- they define a family of expressions, each with a different value. For example, in the function f(x) = x^2 + x + 1 the value of x in the right-hand-side expression doesn't change in the same sense that variables in imperative languages change. But it allows the single expression "x^2 + x + 1" to have a value which varies by the value of x. For example, f(2) yields the value 7 while f(3) yields the value 13.
- clusmore 10y agoGerald Sussman covers the Tower of Hanoi problem in the SICP lectures [1]. The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs - it simply is never optimal to do so anyway. And the solution is so simple, I wonder if you could invent a game by first coming up with a solution and then seeing what it actually solves. [1] https://youtu.be/dlbMuv-jix8?t=47m17s https://youtu.be/dlbMuv-jix8?t=47m17s
- jawarner 10y agoGrant Sanderson has a beautiful video on the Towers of Hanoi problem too [1], part of his animated math project. [1] https://www.youtube.com/watch?list=PLZHQObOWTQDMRtm8h9bG9P06WINNoBnCR&v=2SUvWfNJSsM https://www.youtube.com/watch?list=PLZHQObOWTQDMRtm8h9bG9P06...
- clusmore 10y agoWow, fantastic insight. Thanks for sharing.
- khedoros1 10y ago> The thing I find fascinating about this solution is that it doesn't even require the rule that you can't place larger discs on smaller discs - it simply is never optimal to do so anyway. It seems like without that rule, the game's solution is 2n-1 steps (dump n-1 disks from the left to the right, move disk n to the center, then un-invert those n-1 disks on top of disk n), rather than 2^n-1 moves.
- clusmore 10y ago>dump n-1 disks from the left to the right, move disk n to the center, then un-invert those n-1 disks on top of disk n In the case where you can place larger disks on top of smaller disks, the sub-problems don't have the same solutions, i.e. In order to move N disks from A to B you first move N-1 disks from A to C, then one disk from A to B, then the N-1 disks back from C to B. But in order to solve the N-1 disks, you don't need to ensure that the largest disk ends up on the bottom -- you just move them all straight to the target. I guess the rule is implicitly tied up in the fact that the sub-problems are solved in the same way as the larger problem.
- lutusp 10y agoQuote: "These are variables, and when I've been teaching people to program sometimes I see the light dawn when they realise that a variable name is like a box with the name on the outside." Yes. Maybe there could be some algebra in advance of -- or alongside -- early coding lessons, where this idea is central to both fields. One variable name, any numeric value. It's the same with functions, the lifeblood of analysis -- one function name, any equation. So in a perfect world, people would be learning calculus and general analysis while writing their first program functions -- indeed, they might be learning higher math while coding their lesson materials at the same time. http://arachnoid.com/calculus http://arachnoid.com/calculus
- charles-salvia 10y agoThe best way I've found to introduce the concept of recursion is to explain it like trying to escape from a maze. Suppose at your starting position you have 3 possible corridors to try, in search of the exit. You mark your current position (using bread crumbs or whatever), then try each corridor. If the corridor is a dead end you return to where you left the bread crumb and try another corridor. If one of the corridors leads you to a room with yet more corridors, you leave another bread crumb to mark your position, and then recursively try each of those corridors. Each time you hit a dead end, you'll be able to back track to the last crumb you left. Eventually, you'll find a corridor that leads to the exit. (At that point the metaphor breaks a little because stack unwinding would require you to go back and clean up all your crumbs, but whatever. Maybe a better metaphor would be collecting some items from all the corridors in the maze, and bringing them back to your starting position.)
- clusmore 10y agoMy favourite analogy is that of finding out which row you are in at the cinema. You don't know which row you are, but you know you're 1 behind the guy in front of you, so you ask him and figure you'll just add 1 to that. He doesn't know either, and using the same strategy he asks the person in front of him. Eventually, the guy in the second row asks the guy in the first row, who immediately says he's in the first row. Then each person adds 1 to the answer they get back and feed it back until eventually you get your answer.
- charles-salvia 10y agoThat's a good analogy - the problem is a student could reasonably ask "why would you do it this way"? - i.e. this kind of algorithm seems like a better candidate for iteration. Instead of asking the guy in front of you, get up and count the rows. I know it's for teaching purposes of course, but I'd like the analogy to involve a task that requires that you try something, then back track to some earlier state, then try a different thing, etc. Of course, I guess this just highlights how all the toy examples we see in CS courses often use trivial things like computing Fibonacci sequences or factorials, which are much easier to do iteratively. This often leaves students wondering why anyone would ever even use recursion, or at best, makes it seem like recursion vs. iteration is a mere stylistic choice.
- crooked-v 10y agoTo think about recursion, first, think about recursion.