Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Stop Telling Students Recursion is Hard

jinfiesto.posterous.com

Post reply on HN
Print view View original

91–100 of 111 posts

Re: Stop Telling Students Recursion is Hard

#91

Post by SkyMarshal »

mzl wrote: post #37

When teaching our students concurrent programming using Erlang we never actually mentioned recursion and state immutability. With some careful hand-holding in the first exercises, most of the students seemed to be able to do fine. During three years of teaching the class, only two students ever asked me about immutability ("why can't I change the value of this variable?"). Recursion went similarly unnoticed, it was j…

That's probably the best approach. If you tell students it's 'not hard', they'll immediately suspect your motives and come to the conclusion it actually is hard. If you tell them it's hard, most will believe you. Probably better just to not qualify it and slip it into the lesson when they're not expecting it.

Re: Stop Telling Students Recursion is Hard

#92

Post by charlieflowers »

jinfiesto wrote: post #28
colomon wrote: post #18

On the one hand, I'm in total agreement that we shouldn't tell students recursion is hard. It's a very natural analog to proof by induction, after all. It's an important basic component of programming. On the other hand, "IMHO, recursion is much more natural than iteration and ought to be taught first" is just nuts. I mean, look at the first definition of his example function at http://en.wikipedia.org/wiki/Exponenti…

I don't think the example I've given is iterative. It generates a recursive process. You're right on a different point though, this example is much more efficiently implemented iteratively. The point was to illustrate that writing recursive functions is not difficult. I guess we don't see eye to eye on recursion being taught first. :p In my opinion, recursions analog to "the real world" is much more intuitively obvio…

Actually, I think your example generates an iterative process, not a recursive process. In other words, according to what I read in SICP recently (working through it the first time), I think your example is a recursive function that generates an iterative process.

It's an iterative process because incoming function arguments capture a snapshot of its state at any point, and therefore you don't need state that exists deeper on the call stack. The upshot is that iterative processes are more efficient in terms of how much stack space they use.

Not trying to nitpick -- I enjoyed your post and it is still relevant. Also, I could be wrong, so someone please correct me if so.

Re: Stop Telling Students Recursion is Hard

#93

Post by brlewis »

dkarl wrote: post #84
brlewis wrote: post #63

Earlier quoted context omitted.

I've been hearing experienced programmers opine for a long time that while is the more natural representation of repetitive tasks. Twelve years ago my oldest was learning to walk upstairs. I watched her say "up", go up one stair, then say "up" again, and go up the next stair. This concrete example of recursively calling the "up" function did more to convince me that recursion is natural than any explanation with abst…

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.

Re: Stop Telling Students Recursion is Hard

#94

Post by infinite8s »

cabalamat wrote: post #46
dkarl wrote: post #30

Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition. That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a g…

> 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.

Re: Stop Telling Students Recursion is Hard

#95

Post by infinite8s »

dkarl wrote: post #87
brlewis wrote: post #69

Earlier quoted context omitted.

I agree that it's equivalent in practice; both programs could compile to the same machine code. Where it's different is the human thinking represented by the two programs. The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. It's a conceptually simpler program, up until the point we use that fancy mathematical r-word to descri…

The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. I disagree. The word "while" does connote time, but it's just the word chosen by early programmers to describe a process of performing an action immediately depending on current conditions, with no knowledge of history. Recursion amounts to the same thing -- after you make t…

They are only nested given the common assumption (among programmers, at least) that recursion a stack-like model. From the young child's perspective this is probably tail-recursive operation:

  def up():
     if not at top stair:
         up()
Think of recursion in terms of induction. No nested state required.

Re: Stop Telling Students Recursion is Hard

#96

Post by infinite8s »

silentbicycle wrote: post #70
dublinclontarf wrote: post #41

Earlier quoted context omitted.

Why that is the best simple explanation of continuations I have come across yet. Totally right, it's like thinking about how you are able to walk, if you do it trips you up. Dont think about the details just the concepts.

It's not something people are used to talking explicitly about; it's so ingrained that stuff returns directly to what called it that it never occurs to them. Exceptions are probably the only exception, but I'm not aware of any language besides Common Lisp where an error doesn't unwind the stack - "an exception makes it return several levels up, where the last handler was defined" still fits within a fundamentally sta…

Actually, that description of exceptions requires a stack-based mental model. With true continuations, you have other possibilities for handling the exception (see for example Haskell).

Re: Stop Telling Students Recursion is Hard

#97

Post by [deleted] »

btilly wrote: post #90
Retric wrote: post #56

Earlier quoted context omitted.

You can talk about "divide and conquer" but the most common problem where recursion really helps is looking at tree data structures. As then to consider looking for the total of some value stored in an XML tree. In an iterative language it's a for loop and then calling the function on each of the children. In a Lisp it's calling it's self on the child and next node. PS: Showing someone they can transform a recursion…

Yes, recursion is a natural way to walk through a recursive data structure, like a tree. However if you only know how to reach for recursion, you're completely hosed the second you need a breadth-first search instead. (I've watched candidates completely collapse when faced with that problem.)

[deleted]

Re: Stop Telling Students Recursion is Hard

#98

Post by infinite8s »

btilly wrote: post #90
Retric wrote: post #56

Earlier quoted context omitted.

You can talk about "divide and conquer" but the most common problem where recursion really helps is looking at tree data structures. As then to consider looking for the total of some value stored in an XML tree. In an iterative language it's a for loop and then calling the function on each of the children. In a Lisp it's calling it's self on the child and next node. PS: Showing someone they can transform a recursion…

Yes, recursion is a natural way to walk through a recursive data structure, like a tree. However if you only know how to reach for recursion, you're completely hosed the second you need a breadth-first search instead. (I've watched candidates completely collapse when faced with that problem.)

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])

Re: Stop Telling Students Recursion is Hard

#99

Post by silentbicycle »

infinite8s wrote: post #96
silentbicycle wrote: post #70

Earlier quoted context omitted.

It's not something people are used to talking explicitly about; it's so ingrained that stuff returns directly to what called it that it never occurs to them. Exceptions are probably the only exception, but I'm not aware of any language besides Common Lisp where an error doesn't unwind the stack - "an exception makes it return several levels up, where the last handler was defined" still fits within a fundamentally sta…

Actually, that description of exceptions requires a stack-based mental model. With true continuations, you have other possibilities for handling the exception (see for example Haskell).

That's _exactly_ my point. Exceptions (as typically implemented) fit within a stack-based mental model, Common Lisp's resumable exceptions and first-class continuations do not.

Re: Stop Telling Students Recursion is Hard

#100

Post by btilly »

infinite8s wrote: post #98
btilly wrote: post #90

Earlier quoted context omitted.

Yes, recursion is a natural way to walk through a recursive data structure, like a tree. However if you only know how to reach for recursion, you're completely hosed the second you need a breadth-first search instead. (I've watched candidates completely collapse when faced with that problem.)

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 think of that version because you're familiar with how the recursive solution manages the stack. If you're familiar with that, then switching from dfs to bfs is just a question of replacing a stack with a queue. Compare:

  def dfs(search_node, root_node):
      nodes_to_visit = [root_node]
      while 0
Now contrast the two obvious recursive variations.

  def dfs_recursive(search_node, root_node):
      if search_node == root_node:
          return root_node
      for child_node in root_node.children:
          answer = dfs_recursive(search_node, child_node)
          if answer is not None:
              return answer
      return None

  def bfs_recursive(search_node, root_node):
      nodes_to_visit = []
      def _recurse():
          if 0 == len(nodes_to_visit):
              return None
          node = nodes_to_visit.pop()
          if node == search_node:
              return node
          else:
              nodes_to_visit.extend(node.children)
              return _recurse()
      
      return _recurse()
Post reply on HN