I always found talking about stories about stories about stories a very easy way to get it across. Humans intrinsically get stories.
Stop Telling Students Recursion is Hard
101–110 of 111 posts
Re: Stop Telling Students Recursion is Hard
#102Earlier quoted context omitted.
A breadth-first search can be easily handled with recursion (in fact, I'd argue the specification is almost as simple): def bfs(search_node, nodes_to_visit): node = nodes_to_visit.pop() if node == search_node: return node else: nodes_to_visit.extend(node.neighbors) return bfs(search_node, nodes_to_visit) bfs(search_node, [root_node])
If it is so easy, why does your implementation crash if the element is not in the tree? :-P After you fix that minor bug, you'll find that your code crashes for trees with over 1000 nodes. That is also easy to fix. But in any language without tail recursion, your implementation hits the stack hard. Which in many multi-threaded environments may not be not a wise thing to do. All that said, I submit that you easily thi…
Well, I agree with you there. Any language that can't handle proper tail recursion makes it really difficult to safely implement a recursive solution. But I often find it easier to solve a problem with a recursive solution and perform an almost mechanical conversion into the corresponding iterative solution. (also I'm embarrassed that I forgot the edge case where the node is not in the tree)
Re: Stop Telling Students Recursion is Hard
#103Earlier quoted context omitted.
If it is so easy, why does your implementation crash if the element is not in the tree? :-P After you fix that minor bug, you'll find that your code crashes for trees with over 1000 nodes. That is also easy to fix. But in any language without tail recursion, your implementation hits the stack hard. Which in many multi-threaded environments may not be not a wise thing to do. All that said, I submit that you easily thi…
Well, I agree with you there. Any language that can't handle proper tail recursion makes it really difficult to safely implement a recursive solution. But I often find it easier to solve a problem with a recursive solution and perform an almost mechanical conversion into the corresponding iterative solution. (also I'm embarrassed that I forgot the edge case where the node is not in the tree)
We all make silly errors. Your bfs was a complicated dfs, and neither of us noticed. (In fact I copied your code and edited it, and had dfs and bfs reversed.)
Luckily I was able to edit my node to hide my variation of the error.
Re: Stop Telling Students Recursion is Hard
#104Interestingly enough, in curriculums that start out with functional languages (e.g. Scheme) students have little trouble with recursion... and then consider iterative loops to be "hard".
Wow, that's surprising, I'd love to hear about some (anecdotal) evidence supporting this.
In college they tried to teach us recursion using C and I didn't get it. Later I discovered The Little Schemer and SICP and it just clicked. It's easier to do in Scheme/Lisp, and those books also explain it better. There's one anecdote. :)
Re: Stop Telling Students Recursion is Hard
#105Earlier quoted context omitted.
Both iteration and recursion result in repeated operations. Either way you define the operation of going up a flight of stairs, it's going to involve going "up" a step over and over again, so there's no way to know which way your kid was thinking just from the fact that she said "up" over and over again. In the "while" scenario, the higher-level function "up the staircase" is done once and the lower-level function "u…
Thinking recusively doesn't necessitate a mental model of the stack. See pg's comment.
Obviously not -- recursion isn't limited to computing. However, nested meanings is inherent in recursive definitions because recursion means defining something in terms of itself. If you come up with a recursive idea that happens to be amenable to tail-call optimization, then you will be able to forget about the nesting, but that only happens through work or luck. Forgetting about the nesting is an implementation hack. Consider the classic example of the Von Neumann ordinals:
0 = {}
n + 1 = n ∪ {n}
3 = 2 ∪ {2} = 1 ∪ {1} ∪ {1 ∪ {1}} etc.
f(1) = 1
f(n+1) = (n+1) * f(n)
If you believe that people naturally conceive of recursive ideas, then what happens when their ideas aren't easily transformed to a tail-recursive form? Is that why babies cry all the time? Perhaps by the time we are small children we have learned to subconsciously discard all recursive ideas that we can't transform into a tail-recursive form? If there is a part of my brain that naturally generates tail-recursive solutions to problems but won't plague me with frustrating non-tail-recursive solutions, I would love to tap into it.
Re: Stop Telling Students Recursion is Hard
#106Earlier quoted context omitted.
int pow(int b, int e) { return b * ((e==1)?1:pow(b,e-1)); }
Yes, the author defines exponentiation in terms of recursion. My point is that is not the natural definition of exponentiation, and my evidence is the Wikipedia page, which (as of the time of my original posting of the link, anyway), gives an iterative definition of exponentiation first -- the exact same one I learned in grade school -- and then several pages later mentions a recursive definition as a one-sentence as…
I'm having problems finding the examples you mention in the wikipedia article. That notwithstanding, I disagree that either method is "natural." Iteration is just what they taught you as a child. If we taught recursion instead (specifically for exponents), then that would be the "natural" method.
The point with my C function is that it's certainly simple to do in a non-functional language.
Re: Stop Telling Students Recursion is Hard
#107Earlier quoted context omitted.
I am not sure if I understand recursion or not. My definition of recursion is a function that calls itself repeatedly until an exit condition occurs (the first chapters of little schemer define this as an empty list). If the exit condition never occurs, and the computer lacks infinite computing power, you will probably get a stack overflow. As far as I can tell, recursion and a for-loop accomplish the same thing. Am…
You aren't missing anything, but recursion can get more complicated. In the case of towers of Hanoi, or recursion on trees, the iterative version using a for-loop becomes substantially more complicated than the recursive version. Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So in Scheme this will actually produce an infinite loop with…
Thanks for your answer.
>Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps.
So that is why people make such a big deal about tail-call optimization? Because it prevents stack overflow?
Re: Stop Telling Students Recursion is Hard
#108Earlier quoted context omitted.
You aren't missing anything, but recursion can get more complicated. In the case of towers of Hanoi, or recursion on trees, the iterative version using a for-loop becomes substantially more complicated than the recursive version. Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So in Scheme this will actually produce an infinite loop with…
Thanks for your answer. >Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So that is why people make such a big deal about tail-call optimization? Because it prevents stack overflow?
Yes.
Re: Stop Telling Students Recursion is Hard
#109Earlier quoted context omitted.
> but telling them that it's a familiar idea that they already implicitly understand isn't a good idea either. But people do implicitly understand recursion. Your ancestors are your parents and their ancestors. Your descendants are your children and their descendants. Most people understand the previous two sentences. > As soon as they figure out that for and while loops are sufficient to express all the programming…
Any self-recursive algorithm (and possibly mutually-recursive - I haven't thought about it enough) can be expressed with an iterative algorithm if you use a stack-based structure to maintain state.
Yes, that's essentially implied by the Church-Turing thesis. :)
Re: Stop Telling Students Recursion is Hard
#110Earlier quoted context omitted.
The problem with doing away with the implementation specific details of recursion is that these details are inextricably linked to the correctness of your program in most languages. The fact is, even with modern optimizing compilers that prove all sorts of correctness theorems about transformations, stack overflows will occur in recursive programs if you aren't constantly aware of their existence. You always have to…
I just tried, and ghci (i.e. Haskell) does not blow up when confronted with > let f n = if n > 0 then n + f (n - 1) else 0 > f 1000000
...which is why we should be using lazy languages.