Perhaps the other problem is that it's not obvious to students what the point of doing things recursively is. OK, it can shave a few characters off your factorization code. Or your Fibonacci code. That's neat, but why get excited?
I tell them that recursive code is rarely better than iterative code, but for certain types of problems, it's SO much easier to come up with a recursive solution that it's worth knowing how to do.
Am I missing anything?
EDIT: I wrote this before reading the article
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 no stack overflow:
(define (loop)
(loop))
(loop)>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?
By contrast, in order to calculate the number of nodes in a binary tree, you would do
(nodes (tree)
(if (tree? tree)
(1+ (nodes (left-node tree))
(nodes (right-node tree)))
0))
As a general statement, this is wrong. Recursive code is almost always better than imperative code in languages designed to encourage recursion -- I'm thinking of functional languages here, of course. Please qualify your statements to your students, lest they get the idea that it is a problem with recursion as a principle rather than a problem with the language they're working in.
I just think that recursion falls into the category of things that professors think are neat rather than the category of things that are useful to students. Some students will love that kind of thing, others will wonder what the hell the point is.
Moving on, dynamic programming is a very important technique. About half the time it is easier for me to figure out a dp solution by writing a recursive solution with memoization than it is to build the solution bottom up.
The single most studied problem in computer science is sorting, for the simple reason that a surprising fraction of computing time spent is spent doing sort operations. Virtually every efficient sort algorithm uses recursion somewhere.
The fact that a lot of students won't go on to use recursion doesn't mean that it isn't a very useful technique.
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 function into a while loop if they keep track of their own stack seems to help. Yea, you can write it that way, but recursion really is simpler. (This also helps explain what a stack really is.)
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])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 < len(nodes_to_visit):
node = nodes_to_visit.pop()
if node == search_node:
return node
else:
nodes_to_visit.extend(node.children)
return None
def bfs(search_node, root_node):
nodes_to_visit = [root_node]
while 0 < len(nodes_to_visit):
node = nodes_to_visit.pop(0)
if node == search_node:
return node
else:
nodes_to_visit.extend(node.children)
return None
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()Luckily I was able to edit my node to hide my variation of the error.
Most examples are toys (fib, towers of hanoi, maze solving) or problems that are already solved, sorting, searching, etc.