azule wrote:Related question: is there ever good case for recursion over simple loops?
Some problems are more naturally expressed/solved in a recursive manner.
As a more concrete answer, pretty much the prototypical example of something that is much more naturally written recursively even in a very-imperative language like C are tree operations where you have to descend, do something, come back up, and do something else, as in any traversal. (I'm not sure what your background is, so don't know how much this makes sense. If you know what linked lists are but not trees, a tree is like a linked list but where instead of each node having a single successor, it can have multiple.)
Without recursion, you essentially have to maintain a stack yourself. Here's an example tree traversal:
Code: Select all
def __init__(self, v, l = None, r = None):
self.value = v
self.left = l
self.right = r
two = Node(2)
three = Node(3)
four = Node(4)
two_plus_four = Node(" + ", two, four)
six_times_three = Node(" * ", two_plus_four, three)
recursive_traverse(six_times_three) # should print "(((2) + (4)) * (3))"
I actually tried writing an iterative version... but I don't trust myself to do something correct without thinking about it more than I feel like right now. (It's getting late.)
Another example of a class of problems that are neatly solved with recursion are backtracking algorithms. A canonical example of a backtracking algorithm would be a maze-solving algorithm. If it comes to an intersection, it picks a direction and tries to go that way, in a recursive call. When it runs out of ways to go, it returns up the call chain and tries the next path.
Code: Select all
# Consider 'position' to be a tuple (row,col)
return (position.row - 1, position.col)
return (position.row, positon.col + 1)
# similar for south & west
def can_go_north_from(self, position):
.... # check the actual maze walls
... # other directions
def _maze_solve_helper(maze, position, visited):
if position in visited:
solution_maybe = maze_solve(maze, north(position))
return ["north"] + solution_maybe
solution_maybe = maze_solve(maze, east(position))
return ["east"] + solution_maybe
solution_maybe = maze_solve(maze, south(position))
return ["south"] + solution_maybe
solution_maybe = maze_solve(maze, west(position))
return ["west"] + solution_maybe
return _maze_solve_helper(maze, maze.starting_position(), set())
or something like that.
[Incidentally, these two problems are not actually all that far apart.]