Examples of Recursive functions [closed]

Question

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.

Answer 1

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;
}

Answer 2

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.)

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.