4 ms·

Again, mazes and Towers of Hanoi are neat, but still not exactly what you'd call problems with real-world applicability. There must be some out there -- some ty

by hugh3 16y ago

Again, mazes and Towers of Hanoi are neat, but still not exactly what you'd call problems with real-world applicability. There must be some out there -- some types of parsers, perhaps? Are there any matrix operations which are best done recursively? 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.

zheng 16y ago
Yes, exactly, recursive descent parsers are what they sound like. I'm not very up on other types of parsers, but this is the kind I learned about, and I would say they are very intuitive. http://en.wikipedia.org/wiki/Recursive_descent_parser http://en.wikipedia.org/wiki/Recursive_descent_parser
djjose 16y ago
One of the projects in my CS program using recursion was a 6-degrees of Kevin Bacon game. It was neat and real-world practical IMO.
btilly 16y ago
Any "divide and conquer" algorithm is likely to be recursive. Thus, for instance, the FFT, the Karatsuba multiplication algorithm for large integers, Strassen's matrix multiplication algorithm for matrices and the like are all recursive. 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.
- Retric 16y ago
  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 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.)
  - btilly 16y ago
    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 16y ago
      [deleted]
    - infinite8s 16y ago
      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])
      - btilly 16y ago
        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 < 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 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()
derleth 16y ago
Try writing a program that does complex things with trees (directory structures, for example) without using recursion.
roel_v 16y ago
Graph problems would be hard without recursion I think. I've been working on some problems that are naturally expressed as graphs, and recursion is the natural way to do some things; it's be quite hard to do some things I did iteratively, now that I think about it (that is, without 'emulating' recursion with an 'explicit', manually-maintained stack).
- eru 16y ago
  Yes. Though breadth-first approaches look much more imperative than depth-first traversals. That's because basically you exchange the stack for a queue. (Those algorithms can still look nice in, say, Haskell.)
cousin_it 16y ago
If you're writing a 3d engine, you may encounter many tree-like structures and recursive operations on them: BSPs, quadtrees, octrees, triangle trees for variable LOD terrain...
arethuza 16y ago
I'd have said quicksort is an example of an algorithm where the easiest way to think of is recursively.
- eru 16y ago
  And while you're at it, quickselect, too.
ericmoritz 16y ago
This is the reason why I'm never get excited about recursion. I hardly ever find a real world application for it aside from a tree transversal. Most examples are toys (fib, towers of hanoi, maze solving) or problems that are already solved, sorting, searching, etc.

by hugh3 16y ago

zheng 16y ago

Yes, exactly, recursive descent parsers are what they sound like. I'm not very up on other types of parsers, but this is the kind I learned about, and I would say they are very intuitive. http://en.wikipedia.org/wiki/Recursive_descent_parser http://en.wikipedia.org/wiki/Recursive_descent_parser

djjose 16y ago

One of the projects in my CS program using recursion was a 6-degrees of Kevin Bacon game. It was neat and real-world practical IMO.

btilly 16y ago

Any "divide and conquer" algorithm is likely to be recursive. Thus, for instance, the FFT, the Karatsuba multiplication algorithm for large integers, Strassen's matrix multiplication algorithm for matrices and the like are all recursive. 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.

Retric 16y ago
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 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.)
- btilly 16y ago
  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 16y ago
    [deleted]
  - infinite8s 16y ago
    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])
    - btilly 16y ago
      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 < 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 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()

derleth 16y ago

Try writing a program that does complex things with trees (directory structures, for example) without using recursion.

roel_v 16y ago

Graph problems would be hard without recursion I think. I've been working on some problems that are naturally expressed as graphs, and recursion is the natural way to do some things; it's be quite hard to do some things I did iteratively, now that I think about it (that is, without 'emulating' recursion with an 'explicit', manually-maintained stack).

eru 16y ago
Yes. Though breadth-first approaches look much more imperative than depth-first traversals. That's because basically you exchange the stack for a queue. (Those algorithms can still look nice in, say, Haskell.)

cousin_it 16y ago

If you're writing a 3d engine, you may encounter many tree-like structures and recursive operations on them: BSPs, quadtrees, octrees, triangle trees for variable LOD terrain...

arethuza 16y ago

I'd have said quicksort is an example of an algorithm where the easiest way to think of is recursively.

eru 16y ago
And while you're at it, quickselect, too.

ericmoritz 16y ago

This is the reason why I'm never get excited about recursion. I hardly ever find a real world application for it aside from a tree transversal. Most examples are toys (fib, towers of hanoi, maze solving) or problems that are already solved, sorting, searching, etc.