Examples of Recursive functions

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

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 2

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

Answer 3

The rule of thumb for recursion is, "Use recursion, if and only if on each iteration your task splits into two or more similar tasks".

So Fibonacci is not a good example of recursion application, while Hanoi is a good one.

So most of the good examples of recursion are tree traversal in different disquises.

For example: graph traversal - the requirement that visited node will never be visited again effectively makes graph a tree (a tree is a connected graph without simple cycles)

divide and conquer algorithms (quick sort, merge sort) - parts after "divide" constitute children nodes, "conquer" constitues edges from parent node to child nodes.

Answer 4

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 5

Write a recursive descent parser!

Answer 6

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, 1);
  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 2⁶⁵⁵³⁶ − 3.

Answer 7

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

Answer 8

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 9

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 10

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 11

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.

Answer 12

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

Answer 13

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)

Answer 14

My personal favorite is Binary Search

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

Answer 15

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

Answer 16

My favorite sort, Merge Sort

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

Answer 17

• Factorial
• Traversing a tree in depth (in a filesystem, a game space, or any other case)

Answer 18

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.

Answer 19

How about anything processing lists, like:

• map (and andmap, ormap)
• fold (foldl, foldr)
• filter
• etc...

Answer 20

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.

Answer 21

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.

Answer 22

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