You've already received plenty of good answers, but I'm sick and bored this morning, so I'll add my version to the mix. Many examples of recursion use the factorial problem, which I don't care for, as it's more easily and efficiently implemented as a loop. With an example like that, it's hard to "get" recursion, as many students will think that recursion is simply a crappy way to do a loop. The Tower of Hanoi, mentioned earlier in this thread is a really good recursion example. The one I like is the quicksort algorithm, which is the one I work through below.
Suppose you need to write a function that sorts a list of numbers:
sub list_sort { my @vals = @_; ... code to sort list ... return @sorted_list; }
There are lots of ways to sort lists, some of which you probably already know. But ignore that for now. At some point, when thinking about the problem, you might notice that you can break the problem into a combination of smaller pieces.
As an example, suppose you break your list down into two lists: all numbers smaller than some threshold in the first list, and all the remaining numbers in the second list. Then you could sort your list by sorting the two smaller lists and concatenating them, something like:
sub list_sort { my @vals = @_; my @smaller = get_smaller(@vals); my @larger = get_larger(@vals); return list_sort(@smaller), list_sort(@larger); }
The first condition to using recursion is that you must be able to break the original problem into a combination of smaller parts.
So, what's the second condition to using recursion? Simply put, it's having a way to *stop* using recursion. Typically, when you break a problem into smaller and smaller parts, you'll reach a point where you have a trivial (degenerate) solution--one where you know the answer already.
In the example of sorting a list, where we're breaking the list into smaller and smaller pieces, eventually we'll reach a point where our list contains 0 or 1 items. If you have 0 or 1 items in a list it's already sorted, so you can simply return the list.
This means that our sorting routine turns into something like:
sub list_sort { my @vals = @_; # trivial case: 0 or 1 items in the list return @vals if @vals < 2; my @smaller = get_smaller(@vals); my @larger = get_larger(@vals); return list_sort(@smaller), list_sort(@larger); }
With that, our sort routine is pretty much done. For recursive routines, if you can describe the problem as a combination of smaller versions of the problem, and there's a terminating condition, you can create a recursive routine to solve it. The general form is normally just like that one above: return the answer if it's trivial, otherwise break the problem into one or more smaller parts, solve those, and compute the result from the smaller parts.
The only detail we've left out in our list_sort routine is the part where we split the list into two smaller lists. This is typically the tricky part of a recursive routine: knowing how to split and combine the results to get the answer. For our sort, we have to split our input list into two lists such that all the values in the first list are smaller than all the values in the second list. How do we do that? If we just choose an arbitrary value out of the air, we could easily choose a value that's lower or higher than *all* numbers in our list, in which case we wouldn't be breaking the problem into smaller parts: one of the lists would be the *same* as the input list, so we'd fail the first condition--we wouldn't be breaking the problem into smaller parts.
The inventor of quicksort had a clever idea: Use the first number of the incoming list as the threshold to split the original list. By doing so, we can *remove* the first number from the problem entirely, thus guaranteeing that the two remaining sorts would be smaller than the original list. The routine morphs into something like this:
sub list_sort { my @vals = @_; # trivial case: 0 or 1 items in the list return @vals if @vals < 2; my $split_val = shift @vals; my @smaller = grep { $_ < $split_val } @vals; my @larger = grep { $_ > $split_val } @vals; return list_sort(@smaller), list_sort(@larger); }
Here's a demo script that does our list sort, but with some extra junk in it to tell you what's happening so you can see it in action:
$ cat qsort.pl #!/usr/bin/env perl # # example of recursion using quicksort # use strict; use warnings; # quicksort -- recursively sort a list by taking the first # element and using that as the "center" value, and breaking # the rest of the list into two lists: those lower than the # center value and those higher than the center value. # # then return qsort(lower), center, qsort(higher) # # The degenerate case is when you have a single value in your # list -- simply return it. # # This version helps illustrate the recursion by describing # what it's doing, with indentation to show the nesting of the # calls. # sub list_sort { my ($lev, @vals) = @_; #print " "x$lev, "qs(", join(" ", @vals), ")\n"; print " "x$lev, "qs(@vals)\n"; ++$lev; if (@vals < 2) { print " "x$lev, "degenerate case, returning (@vals)\n"; return @vals; } my $split_val = shift @vals; my @lower = grep { $_ lt $split_val } @vals; my @higher = grep { $_ gt $split_val } @vals; print " "x$lev, "(@lower), $split_val, (@higher)\n"; @vals = ( list_sort($lev, @lower), $split_val, list_sort($lev, @higher) ); print " "x$lev, "returning (@vals)\n"; return @vals; } my @list = qw(c a h f g e b d i); print "ORIG: @list\n"; @list = list_sort(0, @list); print "DONE: @list\n"; $ perl qsort.pl ORIG: c a h f g e b d i qs(c a h f g e b d i) (a b), c, (h f g e d i) qs(a b) (), a, (b) qs() degenerate case, returning () qs(b) degenerate case, returning (b) returning (a b) qs(h f g e d i) (f g e d), h, (i) qs(f g e d) (e d), f, (g) qs(e d) (d), e, () qs(d) degenerate case, returning (d) qs() degenerate case, returning () returning (d e) qs(g) degenerate case, returning (g) returning (d e f g) qs(i) degenerate case, returning (i) returning (d e f g h i) returning (a b c d e f g h i) DONE: a b c d e f g h i
...roboticus
When your only tool is a hammer, all problems look like your thumb.
In reply to Quicksort (Re: recursion basics)
by roboticus
in thread recursion basics
by wrinkles
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |