tags:

views:

3053

answers:

22

Can anybody suggest programming examples that illustrate recursive functions? There are the usual old horses such as Fibonacci series and Towers of Hanoi, but anything besides them would be fun.

A: 

My personal favorite is Binary Search

Edit: Also, tree-traversal. Walking down a folder file structure for instance.

Geoff
A: 
  • Factorial
  • Traversing a tree in depth (in a filesystem, a game space, or any other case)
Vinko Vrsalovic
Actually, factorial is often better done using a loop. It's kind of a stupid, tho often used, example
Rik
It may perfrom better in a loop, but it is a well understood idea that easily expressed rescursively especially in languages with partial functions.
Steve g
So many common examples are actually loop-like, simply because the people who use functional languages seem to prefer recursion. In 'normal' programming languages, most things are better done as a loop, both for performance and for readable code.
Marcus Downing
+6  A: 

Write a recursive descent parser!

Martin Cote
A: 

Implementing Graphs by Guido van Rossum has some recursive functions in Python to find paths between two nodes in graphs.

sanxiyn
+20  A: 

This illustration is in English, rather than an actual programming language, but is useful for explaining the process in a non-technical way:

A child couldn't sleep, so her mother told a story about a little frog,
  who couldn't sleep, so the frog's mother told a story about a little bear,
     who couldn't sleep, so bear's mother told a story about a little weasel
       ...who fell asleep.
     ...and the little bear fell asleep;
  ...and the little frog fell asleep;
...and the child fell asleep.
ConroyP
That's quite nice to read.
JosephStyons
Yeah, but where's the end condition/base case? ;-)
Joachim Sauer
@Joachim Weasel is always the base case, dude. _You know this!_
Andres Jaan Tack
Also, this is beautiful.
Andres Jaan Tack
A: 

My favorite sort, Merge Sort

(Favorite since I can remember the algorithm and is it not too bad performance-wise)

crashmstr
Merge sort is awesome :) ... and also one of the few algorithms I actually remember !
anbanm
A: 

How about reversing a string?

void rev(string s) {
  if (!s.empty()) {
    rev(s[1..s.length]);
  }
  print(s[0]);
}

Understanding this helps understand recursion.

Yuval F
Like factorial, reversing a string is much more easily done with a loop.
Kip
Sure it is, but this question requested examples to illustrate recursion, and this example adds something not found in other examples.
Yuval F
+2  A: 

Another couple of "usual-suspects" are Quicksort and MergeSort

agnul
A: 

Here is a sample I posted on this site a while back for recursively generating a menu tree: Recursive Example

JPrescottSanders
A: 

How about anything processing lists, like:

  • map (and andmap, ormap)
  • fold (foldl, foldr)
  • filter
  • etc...
pkaeding
+1  A: 

The hairiest example I know is Knuth's Man or Boy Test. As well as recursion it uses the Algol features of nested function definitions (closures), function references and constant/function dualism (call by name).

Hugh Allen
+2  A: 

The interpreter design pattern is a quite nice example because many people don't spot the recursion. The example code listed in the Wikipedia article illustrates well how this can be applied. However, a much more basic approach that still implements the interpreter pattern is a ToString function for nested lists:

class List {
    public List(params object[] items) {
        foreach (object o in items)
            this.Add(o);
    }

    // Most of the implementation omitted …
    public override string ToString() {
        var ret = new StringBuilder();
        ret.Append("( ");
        foreach (object o in this) {
            ret.Append(o);
            ret.Append(" ");
        }
        ret.Append(")");
        return ret.ToString();
    }
}

var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7);
Console.WriteLine(lst);
// yields:
// ( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 )

(Yes, I know it's not easy to spot the interpreter pattern in the above code if you expect a function called Eval … but really, the interpreter pattern doesn't tell us what the function is called or even what it does and the GoF book explicitly lists the above as an example of said pattern.)

Konrad Rudolph
A: 

From the world of math, there is the Ackermann function:

Ackermann(m, n)
{
  if(m==0)
    return n+1;
  else if(m>0 && n==0)
    return Ackermann(m-1, n);
  else if(m>0 && n>0)
    return Ackermann(m-1, Ackermann(m, n-1));
  else
    throw exception; //not defined for negative m or n
}

It always terminates, but it produces extremely large results even for very small inputs. Ackermann(4, 2), for example, returns 265536 − 3.

Kip
+3  A: 

How about testing a string for being a palindrome?

bool isPalindrome(char* s, int len)
{
  if(len < 2)
    return TRUE;
  else
    return s[0] == s[len-1] && isPalindrome(&s[1], len-2);
}

Of course, you could do that with a loop more efficiently.

Kip
+2  A: 

In my opinion, recursion is good to know, but most solutions that could use recursion could also be done using iteration, and iteration is by far more efficient.

That said here is a recursive way to find a control in a nested tree (such as ASP.NET or Winforms):

public Control FindControl(Control startControl, string id)
{
      if (startControl.Id == id)
           return startControl

      if (startControl.Children.Count > 0)
      {
           foreach (Control c in startControl.Children)
           {
                return FindControl(c, id);
           }
      }
      return null;
}
FlySwat
“and iteration is by far more efficient” -- such blanket statements are almost always false (yet another one ;-)). Use tail recursion and performance is on par with iteration.
Konrad Rudolph
Proponents of functional programming seem to prefer recursion whenever possible, and use the fact that tail recursion == iteration as an excuse. In the real world, recursion comes at a cost.
Marcus Downing
holy! how did you get code off my development box? That is almost exactly character by character and even line spacing, a function i have in my own library.
stephenbayer
stephen, I think we've all written that function more than once :)Konrad, even tail recursion has the added cost of pushing the function arguments to the stack once.
FlySwat
Jon, even iteration, when encapsulated in a function, “has the added cost of pushing the function arguments to the stack once.” So there. Additionally, there's function call inlining which also works for tail recursive functions.
Konrad Rudolph
Not every compiler will do tail call optimizations, and your assuming that the iteration has been placed in a secondary function to begin with, what about iterating in a function instead of calling out to as second function to do recursion? No matter how you slice it, iteration is more efficient.
FlySwat
A: 

Translate a spreadsheet column index to a column name.

It's trickier than it sounds, because spreadsheet columns don't handle the '0' digit properly. For example, if you take A-Z as digits when you increment from Z to AA it would be like going from 9 to 11 or 9 to 00 instead of 10 (depending on whether A is 1 or 0). Even the Microsoft Support example gets it wrong for anything higher than AAA!

The recursive solution works because you can recurse right on those new-digit boundries. This implementation is in VB.Net, and treats the first column ('A') as index 1.

Function ColumnName(ByVal index As Integer) As String
    Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c}

    index -= 1 'adjust index so it matches 0-indexed array rather than 1-indexed column'

    Dim quotient As Integer = index \ 26 'normal / operator rounds. \ does integer division'
    If quotient > 0 Then
        Return ColumnName(quotient) & chars(index Mod 26)
    Else
        Return chars(index Mod 26)
    End If
End Function
Joel Coehoorn
A: 

In order to understand recursion, one must first understand recursion.

Ilya Ryzhenkov
A: 

Once upon a time, and not that long ago, elementary school children learned recursion using Logo and Turtle Graphics. http://en.wikipedia.org/wiki/Turtle_graphics

Recursion is also great for solving puzzles by exhaustive trial. There is a kind of puzzle called a "fill in" (Google it) in which you get a grid like a crossword, and the words, but no clues, no numbered squares. I once wrote a program using recursion for a puzzle publisher to solve the puzzles in order be sure the known solution was unique.

SeaDrive
+1  A: 

Recursive functions are great for working with recursively defined datatypes:

  • A natural number is zero or the successor of another natural number
  • A list is the empty list or another list with an element in front
  • A tree is a node with some data and zero or more other subtrees

Etc.

Bruno De Fraine
A: 

As others have already said, a lot of canonical recursion examples are academic.

Some practical uses I 've encountered in the past are:

1 - Navigating a tree structure, such as a file system or the registry

2 - Manipulating container controls which may contain other container controls (like Panels or GroupBoxes)

JosephStyons
A: 

A real-world example is the "bill-of-materials costing" problem.

Suppose we have a manufacturing company that makes final products. Each product is describable by a list of its parts and the time required to assemble those parts. For example, we manufacture hand-held electric drills from a case, motor, chuck, switch, and cord, and it takes 5 minutes.

Given a standard labor cost per minute, how much does it cost to manufacture each of our products?

Oh, by the way, some parts (e.g. the cord) are purchased, so we know their cost directly.

But we actually manufacture some of the parts ourselves. We make a motor out of a housing, a stator, a rotor, a shaft, and bearings, and it takes 15 minutes.

And we make the stator and rotor out of stampings and wire, ...

So, determining the cost of a finished product actually amounts to traversing the tree that represents all whole-to-list-of-parts relationships in our processes. That is nicely expressed with a recursive algorithm. It can certainly be done iteratively as well, but the core idea gets mixed in with the do-it-yourself bookkeeping, so it's not as clear what's going on.

joel.neely
A: 

Here's a pragmatic example from the world of filesystems. This utility recursively counts files under a specified directory. (I don't remember why, but I actually had a need for something like this long ago...)

public static int countFiles(File f) {
    if (f.isFile()){
        return 1;
    }

    // Count children & recurse into subdirs:
    int count = 0;
    File[] files = f.listFiles();
    for (File fileOrDir : files) {
        count += countFiles(fileOrDir);
    }
    return count;
}

(Note that in Java a File instance can represent either a normal file or a directory. This utility excludes directories from the count.)

A common real world example would be e.g. FileUtils.deleteDirectory() from the Commons IO library; see the API doc & source.

Jonik