[ACCEPTED]-Examples of Recursive functions-recursion

This illustration is in English, rather than an actual programming 2 language, but is useful for explaining the 1 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.

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

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

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

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

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

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

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 2 course, you could do that with a loop more 1 efficiently.

Write a recursive descent parser!

0

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 3 terminates, but it produces extremely large 2 results even for very small inputs. Ackermann(4, 2), for 1 example, returns 2⁶⁵⁵³⁶ − 3.

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

The interpreter design pattern is a quite nice example because many 12 people don't spot the recursion. The example 11 code listed in the Wikipedia article illustrates 10 well how this can be applied. However, a 9 much more basic approach that still implements 8 the interpreter pattern is a ToString function for 7 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 6 to spot the interpreter pattern in the above 5 code if you expect a function called Eval … but 4 really, the interpreter pattern doesn't 3 tell us what the function is called or even 2 what it does and the GoF book explicitly 1 lists the above as an example of said pattern.)

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

That 2 said here is a recursive way to find a control 1 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;
}

Here's a pragmatic example from the world 9 of filesystems. This utility recursively 8 counts files under a specified directory. (I 7 don't remember why, but I actually had a 6 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 5 that in Java a File instance can represent either 4 a normal file or a directory. This utility 3 excludes directories from the count.)

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

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

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

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

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

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

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

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

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

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

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

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

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

My personal favorite is Binary Search

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

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

My favorite sort, Merge Sort

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

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

0

How about reversing a string?

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

Understanding 1 this helps understand recursion.

How about anything processing lists, like:

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

0

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

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

Recursive functions are great for working 1 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.