Recursion without factorial, Fibonacci numbers etc

Question

Almost every article about recursion includes examples with factorial or Fibonacci numbers which are a) math b) useless in real life. Are there some interesting non-math code examples to teach recursion? I'm thinking divide-and-conquer algorithms but they usually involve complex data structures.

Answer 1

Directory / File structures are the best example of a use for recursion, because everyone understands them before you start, but anything involving tree-like structures will do.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}

Answer 2

QuickSort would be the first one that jumps to mind. Binary search also is a recursive problem. Beyond that there are whole classes of problems that solutions fall out almost for free when you start working with recursion.

Answer 3

Towers of Hanoi is a good one to help learn recursion.

There are many solutions to it on the web in many different languages.

Answer 4

A Palindrome Detector:

Start with a string : "ABCDEEDCBA" If starting & ending characters are equal, then recurse and check "BCDEEDCB", etc...

Answer 5

Look for things that involve tree structures. A tree is relatively easy to grasp, and the beauty of a recursive solution becomes apparent far sooner than with linear data structures such as lists.

Things to think about:

• filesystems - those are basically trees; a nice programming task would be to fetch all .jpg images under a certain directory and all its subdirectories
• ancestory - given a family tree, find the number of generations you have to walk up to find a common ancestor; or check whether two people in the tree belong to the same generation; or check whether two people in the tree can legally marry (depends on jurisdiction :)
• HTML-like documents - convert between the serial (text) representation of a document and a DOM tree; perform operations on subsets of a DOM (maybe even implement a subset of xpath?); ...

These are all related to actual real-world scenarios, and they can all be used in applications of real-world significance.

Answer 6

A binary search algorithm sounds like what you want.

Answer 7

Here are some more practical problems that come to my mind:

• Merge Sort
• Binary Search
• Traversal, Insertion and Removal on Trees (largely used on database applications)
• Permutations generator
• Sudoku solver (with backtracking)
• Spell-checking (again with backtracking)
• Syntax analysis (.e.g, a program that converts prefix to postfix notation)

Answer 8

http://stackoverflow.com/questions/105838/real-world-examples-of-recursion

• modelling a contagious infection
• generating geometry
• directory management
• sorting

http://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion

• raytracing
• chess
• parsing source code (language grammar)

http://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence

• BST search
• Towers of Hanoi
• palindrome search

http://stackoverflow.com/questions/126756/examples-of-recursive-functions

• Gives a nice English-language story that illustrates recursion by a bedtime story.

Answer 9

The JavaScript DOM is a good place to play around with recursion.

Answer 10

Sort, defined recursively in Python.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Merge, defined recursively.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Linear search, defined recursively.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Binary search, defined recursively.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )

Answer 11

In functional programming languages, when no higher-order functions are available, recursion is used instead of imperative loops in order to avoid mutable state.

F# is an impure functional language which allows both styles so I will compare both here. The following sum all the numbers in a list.

Imperative Loop with Mutable Variable

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Recursive Loop with No Mutable State

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Note that this kind of aggregation is captured in the higher order function List.fold and could be written as List.fold (+) 0 xlist or indeed even more simply with the convenience function List.sum as just List.sum xlist.

Answer 12

I've used recursion heavily in game playing AI. Writing in C++, I made use of a series of about 7 functions that call each other in order (with the first function having an option to bypass all of those and call instead a chain of 2 more functions). The final function in either chain called the first function again until the remaining depth I wanted to search went to 0, in which case the final function would call my evaluation function and return the score of the position.

The multiple functions allowed me to easily branch based on either player decisions or random events in the game. I'd make use of pass-by-reference whenever I could, because I was passing around very large data structures, but because of how the game was structured, it was very difficult to have an "undo move" in my search, so I'd use pass-by-value in some functions to keep my original data unchanged. Because of this, switching to a loop-based approach instead of a recursive approach proved too difficult.

You can see a very basic outline of this sort of program, see https://secure.wikimedia.org/wikipedia/en/wiki/Minimax#Pseudocode

Answer 13

Another real world recursion problem that students may relate to is to build their own web crawler that pulls information from a website and follows all the links within that site (and all the links from those links, etc).

Answer 14

A really good real life example in business is something called a "Bill of Materials". This is the data that represents all of the components that make up a finished product. For example, let's use a Bicycle. A Bicycle has handlebars, wheels, a frame, etc. And each of those components can have sub-components. for example the Wheel can have Spokes, a valve stem, etc. So typically these are represented in a tree structure.

Now to query any aggregate information about the BOM or to change elements in a BOM often times you resort to recursion.

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

And a sample recursive call...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

Obviously the BomPart Class would have many many more fields. You may need to figure out how many plastic components you have, how much labor it takes to build a complete part, etc. All this comes back to the usefulness of Recursion on a tree structure though.

Answer 15

Family relations make for good examples because everybody understands them intuitively:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);

Answer 16

I solved a problem with a knight pattern (on a chessboard) using a recursive program. You were supposed to move the knight around so that it touched every square except a few marked squares.

You simply:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

Many kinds of "think-ahead" scenarios can be worked by testing future possibilities in a tree like this.

Answer 17

In a sense, recursion is all about divide and conquer solutions, that is breking the problem space into a smaller one to help find the solution for a simple problem, and then usualy going back reconstructing the original problem to compose the right answer.

Some examples not involving math to teach recursion (at least those problems I remember from my university years):

• Towers of Hanoi
• Eight queens

These are examples of using Backtracking to solve the problem.

Other problems are classics of Artificial Intelligence domain: Using Depth First Search, pathfinding, planning.

All those problems involve some kind of "complex" data structure, but if you don't want to teach it with math (numbers) then your choices may be more limited. Yoy may want to start teaching with a basic data structure, like a linked List. For example representing the natural numbers using a List:

0 = empty list 1 = list with one node. 2 = list with 2 nodes. ...

then define the sum of two numbers in terms of this data structure like this: Empty + N = N Node(X) + N = Node(X + N)

Answer 18

A rather useless yet showing recursion inner working well is recursive strlen():

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

No math - a very simple function. Of course you don't implement it recursively in real life, but it's a good demo of recursion.