26

Possible Duplicates:
Real-world examples of recursion
Examples of Recursive functions

I see that most programming language tutorial teach recursion by using a simple example which is how to generate fibonacci sequence, my question is, is there another good example other than generating fibonacci sequence to explain how recursion works?

9
  • 2
    Possible duplicate: stackoverflow.com/questions/105838/…
    – MPelletier
    Feb 9, 2011 at 14:37
  • 11
    Fibonacci really isn't a 'good example of recursion'.
    – Nabb
    Feb 9, 2011 at 15:34
  • Also duplicate of stackoverflow.com/questions/126756/…. (Well, unlike this one, that question isn't tagged C++. But I doubt that is relevant for understanding recursion.)
    – Jonik
    Feb 9, 2011 at 17:01
  • 1
    @Nabb: Why not? I think it’s a phenomenal example because it’s amenable to so many smart optimizations and it can serve to explain not only vanilla recursion but also memoization and dynamic programming. Feb 9, 2011 at 17:36
  • 3
    It's weird how these "Hey, give me an example of ____." questions get so many votes.
    – Inverse
    Feb 9, 2011 at 18:14

23 Answers 23

39

The classic is the binary tree search:

def findval (node,val):
    if node == null:
        return null
    if node.val = val:
        return node
    if node.val > val:
        return findval (node.left,val)
    return findval (node.right,val)

findval (root,thing_to_find)

That may be a little more complex than a simple formula but it's the "bread and butter" use of recursion, and it illustrates the best places to use it, that where the recursion levels are minimised.

By that I mean: you could add two non-negative numbers with:

def add (a,b):
    if b == 0:
        return a
    return add (a+1,b-1)

but you'd find yourself running out of stack space pretty quickly for large numbers (unless the compiler optimised tail-end recursions of course, but you should probably ignore that for the level of teaching you're concerned with).

3
  • is the side note about going out of stack space a bait to revive the python Tail-end recursion troll ? That's definitely a python issue...
    – kriss
    Feb 9, 2011 at 14:46
  • 3
    No, although that looks like Python, it's really pseudo-code (I find Python a very good template for pseudo-code). I was just stating that, if the compiler didn't perform tail-end optimisation, you need to control the stack levels pretty tightly, lest you run out.
    – paxdiablo
    Feb 9, 2011 at 15:10
  • 1
    My fav is :: If you found a good example then you are done otherwise search for example here
    – r15habh
    Jun 25, 2011 at 13:37
29

The other answers mention various algorithms, which is completely fine, but if you want a bit more "concrete" example, you could list all files in some directory and its subdirectories. The hierarchical file system is a well-known example of a recursive (tree) structure, and you could show depth-first and breadth-first search using this concrete example.

1
  • +1. Missed this answer until after I had also supplied the same answer. I've added sample code
    – thrag
    Feb 9, 2011 at 16:41
27

My favourite example for recursion is the Towers of Hanoi: To move a stack of pieces from pole A to pole B, you move everything above the lowest piece to the pole that is not A or B, then move the lowest piece to B, and then you move the stack that you put on the "helper pole" on top of the lowest piece. For the first and third step, you follow this instruction recursively. See the link for a longer explanation :)

2
  • +1. Also, ToH can be tweaked slightly to force you to think even more about the recursion at work; e.g., a ring can only move one pole at a time (no direct A->C), etc. Great practice for recursion! Feb 9, 2011 at 16:09
  • I encountered this recently when reading through JavaScript the good parts. Took me about an hour of thinking and drawing on a whiteboard before I got it and realized what a neat algorithm it is. The difficult part was figuring out what subproblem the algorithm is solving when the parameters get switched around in recursive calls.
    – Sam
    Feb 9, 2011 at 16:12
21

Check for a palyndrome:

bool recursivePalindrome(std::string str, unsigned int index = 0) {
    if (index > str.length()/2) return true;
    else if (str[index] == str[str.length()-index-1])
        return recursivePalindrome(str, ++index);
    else return false;
}

Or on a less serious note :)

void StackOverflow()
{
   StackOverflow();
}
3
  • 13
    Although a good tail-end optimiser will simply convert that to while(1); :-)
    – paxdiablo
    Feb 9, 2011 at 13:37
  • 1
    Doing palindromes non-recursively would seem a lot easier, though: unsigned last = str.size() - 1; while (index < last) if (str[index++] != str[last--]) return false; return true;.
    – visitor
    Feb 11, 2011 at 10:04
  • This comes close to a palindrome and is more serious: :(){ :|: & };:.
    – SiggyF
    Mar 10, 2011 at 7:32
16

How about finding factorial.

int GetFactorial(int n )
{
  if ( n==0) return 1;
  return n*GetFactorial(n-1);
}

The idea is, factorial is defined recursively as the product of n and factorial of (n-1). And from recursive definition, you get your recursion.

4
  • Well, factorial isn't all that different from fibonacci, is it?
    – sbi
    Feb 9, 2011 at 13:01
  • 5
    True, but it's different enough :) Feb 9, 2011 at 13:07
  • 2
    @sbi Unlike fibonacci, calculating factorial recursively is the same big-O runtime as doing it the sensible iterative way, so it's definitely an improvement. On the other hand, it doesn't demonstrate multiple recursive calls. Feb 9, 2011 at 13:40
  • @Nick: You do have a point there, although I still think that the two are quite similar. (Oh, and if you do the fibonacci using template-meta programming, that will avoid repeatedly calculating the same results. :) )
    – sbi
    Feb 9, 2011 at 15:19
12

Traversing the folder hierarchy of a directory tree as part of a file system is a good real-world example. Look into this SO post for a C++ example:

Why am I having problems recursively deleting directories?

2
10
  • Most of the other examples given here are mathematics examples which really just re-illustrate the same application of recursion.
  • The search and sort variants are good algorithm examples but often a bit too complicated for beginners.
  • Towers of Hanoi is a classic but pretty contrived really.

================

The example I use for demonstrating the simple power of recursion is recursive file processing in a directory tree.

Here is a C# example

void ProcessFiles( string sFolder )
{
    foreach( string f in Directory.GetFiles( sFolder ) )
    {
        DoSomethingTo( f );
    }
    foreach( string d in Directory.GetDirectories( sFolder ))
    {
        ProcessFiles( d );
    }
}
10

Merge sort is a pretty good example of an algorithm that is easier to read and understand when implemented recursively.

Here's a little high-level pseudocode version of Merge Sort:

def merge_sort(List sortlist)
    if sortlist.length <= 1 return sortlist
    split sortlist into leftlist and rightlist
    return merge(merge_sort(leftlist), merge_sort(rightlist))   

def merge(List leftlist, List rightlist)
    while(leftlist and rightlist not empty)
        compare leftlist.first to rightlist.first
        pop lowest value off its list and append to resultlist
    append any remains of leftlist onto resultlist
    append any remains of rightlist onto resultlist
    return resultlist

An iterative version of this is would be much more complicated to write and to visualise.

1
  • @back2dos: yep +1, quicksort is another good example. I thought mergesort might be slightly easier to understand in a tutorial situation, but they are basically quite similar.
    – GrahamS
    Feb 9, 2011 at 18:37
5

There are several samples:

Catalan numbers:

T(n) = Sum(T(i)*T(n-i)) for all 1 <= i < n

Ackermann function:

A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.

Simple Maze problem

Finding Hamiltonian Path problem

factorial.

and you can see wiki page for other references.

3
  • The Catalan numbers have a much more efficient iterative/tail-recursive form. Feb 15, 2011 at 0:26
  • @Donal Fellows, Fibonacci numbers iterative algorithm is more powerful than recursive one O(n) versus (O((1+sqrt(5))^n), and if you say you can use memoization, also you can use memoized recursive for catalan numbers. Feb 15, 2011 at 8:18
  • Memoization is indeed applicable in all of those cases, but it's less vital in cases where there's a linear algorithm. It's the truly non-linear algorithms that really benefit though. (Plus, the best examples of recursion involve recursive structures such as filesystems or other types of tree.) Feb 15, 2011 at 8:44
5

Good examples of recursion are often related to cases where underlying data structure or the problem itself is recursive : trees, graphs, algorithms using divide and conquer approach (like many sorts), parser of recursive grammars (like common arithmetic expresions), find strategy for chess-like two players games (for a simple exemple consider Nim), combinatory problems, etc.

3

Try recursive binary search: http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html

Or a recursive quick sort: http://www.dreamincode.net/forums/topic/72311-recursive-quicksort-algorithm/

These are just two small example in a vast world of recursive functions.

3

Evaluation of arithmetic expressions can be done recursively or iteratively using a stack. It can be quite instructive to compare the two approaches.

1

My mother-in-law took an introductory course in C. She had a homework problem, something like:

You have a bar of metal (length len), and a number of orders (n) to cut the metal into various lengths. You want to maximize the amount of metal being used, but cannot exceed the overall length.

The instructor suggested iterating from 1 to 2**n in binary, excluding an order if its corresponding bit were 0 and including an order if its bit were 1, while keeping track of the maximum sum. His proposal would run in polynomial time.

Another solution exists using a recursive knapsack algorithm. You can iterate down from len to 1 and do a depth-first search to recursively find the sum of lengths.

A different area in which I have used recursion was for Huffman coding (for compressing a string), but this does not have the intuitive feel of the knapsack problem.

Recursion is a wonderful concept that is radically different. Best wishes in learning or teaching it.

1

Ackermann function:

/* undefined if m and n are negative */
uint32 ackermann( uint32 m, uint32 n )
{
  if( m < 0 && n < 0 ) { exit(1); /* invalid m and n */ }

  if( m == 0 ){ return n + 1; }

  if( m > 0 && n == 0 ){ return ackermann( m - 1, 1 ); }

  if( m > 0 && n > 0 ){ return ackermann( m - 1, ackermann(m, n - 1) ); }
}

The multiple comparisons of m > 0 are redundant (and can be simplified). Leaving them as-is, however, shows the standard definition of the Ackermann function.

But one does not have to go so far off the mathematical edge to find interesting recursive functions other than the Fibonnaci numbers.

You have the greatest common denominator (GDC) function, quicksort and the always typical binary search algorithm.

1

Anything which has a hierarchy. For example listing all the employees beneath your boss.

1

Recursion finds its fundations in mathematical induction, and should be taught as such.

Defining functions by induction can be exposed clearly with list processing. There are many things to say about fold for instance.

Then, move on to trees.

1

It's not C++, obviously, but the concept is sound:

PHP recursively traversing nested multidimensional arrays:

public function recurse_me($collection) {
    foreach ($collection as $value) {
        if (is_array($value)) {
            $this->recurse_me($value);
        } else {
            // process value.
        }
    }
}
1

I remember that I understood recursion by writing a programm, that searches for word ladders. In a given dictionary.

0

The academic example is the factorial

n!

calculum. In real life, you get math libs.

12
  • 2
    The factorial is good for describing how recursion works. It is a bad example of why you should use recursion (in languages like C++).
    – ℍ ℍ
    Feb 9, 2011 at 13:06
  • @Henk At least it's better than fibonacci. In functional languages, (tail-) recursively is how you'd calculate factorials! Feb 9, 2011 at 13:41
  • @Nick: Actually, that's how you would calculate fibonacci numbers too. Feb 11, 2011 at 10:23
  • @Donal Sure, but loops are done tail-recursively in purely functional languages. Calculating Fibonacci "the recursive way" requires two recursive invocations, so you can't do it tail-recursively. Feb 13, 2011 at 22:42
  • @Nick: Wrong, it requires a more sophisticated function (which can be wrapped). Here's an example in Erlang, but trivially translatable: en.literateprograms.org/… Feb 14, 2011 at 9:13
0

There are sorting algorithms that rely on recursion.

And then, there's the binary search that is implemented with recursion.

2
  • These are little bit complex to understand to explain recursion. Feb 9, 2011 at 12:59
  • 1
    @Gunner, a well-written recursive binary search should be no more than ten lines of code.
    – paxdiablo
    Feb 9, 2011 at 13:06
0

Pascal's triangle

0

Heap sort is also a good example. You can read about it in "Introduction to Algorithms" by Cormen, Rivest and others. Great book, I hope you'll find a lot of interesting there.

0

Lots of operations on linked-node type structures can be recursive. Others have mentioned BSTs, but if you don't want to have to explain what those are, consider searching for the highest value in a linear, unsorted list:

int MaxValue(Node node)
{
    if (node == null)
        return 0;

    if (node.Next == null)
        return node.Value;

    int maxNext = MaxValue(node.Next);
    return node.Value > maxNext ? node.Value : maxNext;
}

Lists (in this case, linked lists) are very easy to explain in real-world terms; your audience doesn't even have to have a programming background. You can simply describe it as a group of unsorted boxes, or a list of numbers.

Not the answer you're looking for? Browse other questions tagged or ask your own question.