# Recursion without factorial, Fibonacci numbers etc

Almost every article I can find about recursion includes the examples of factorial or Fibonacci Numbers, which are:

1. Math
2. 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.

-
In general, if you wait longer before accepting an answer you might get more answers. –  jimreed Sep 13 '11 at 12:14
While your question is completely valid, I'd hesitate calling Fibonacci numbers useless in real life. Same goes for factorial. –  Zach L Sep 13 '11 at 13:48
The Little Schemer is a whole book on recursion that never uses Fact or Fib. junix-linux-config.googlecode.com/files/… –  Eric Wilson Sep 13 '11 at 13:49
@Zach: Even so, recursion is a horrible way to implement Fibonacci numbers, because of the exponential running time. –  dan04 Sep 13 '11 at 18:05
@dan04 unless your language is smart enough to implement tail call optimization like most functional languages in which case it works just fine –  Zachary K Apr 5 '12 at 12:29

## 18 Answers

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;
}
-
Thanks, I think I'll go with filesystem. It's something concrete and can be used for many real-world examples. –  synapse Sep 13 '11 at 11:20
Note : unix command often unclude the -r option (cp or rm for exemple). -r stand for recursive. –  deadalnix Sep 13 '11 at 11:50
you do have to be a little careful here as in the real world file systems are actually a directed graph not necessarily a tree, if supported by the file system, hard links etc. can create joins and cycles –  jk. Sep 14 '11 at 8:05
@jk: Directories cannot be hard linked, so modulo some leaves that might appear in more than one location, and assuming you exclude symlinks, real world filesystems are trees. –  R.. Sep 14 '11 at 12:49
there are other peculiarities in some file systems for directories e.g. NTFS reparse points. my point is that code that isn't specifically aware of this can have unexpected results on real world file systems –  jk. Sep 14 '11 at 12:57

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.

-
Binary search is often formulated as a recursive problem but it's trivial (and often preferable) to implement in an imperative way. –  fluffy Sep 13 '11 at 17:03
@Zachary: Algorithms that can be implemented with tail recursion (like binary search) are in a fundamentally different space class than those which require real recursion (or your own state structures with equally expensive space requirements). I don't think it's beneficial for them to be taught together as if they're the same. –  R.. Sep 14 '11 at 12:52

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

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

-
This is actually in my opinion another bad example. First off, it is unrealistic; it's not a problem people actually have. Second, there are easy non-recursive solutions. (One is: number the disks. Never move a disk onto a disk of the same parity and never undo the last move you made. If you follow those two rules, you'll solve the puzzle with the optimal solution. No recursion required.) –  Eric Lippert Sep 13 '11 at 15:09

A Palindrome Detector:

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

-
That's also trivial to solve without recursion and, IMHO, better solved without it. –  Blrfl Sep 13 '11 at 11:15
Agreed, but OP Specifically asked for Teaching examples with minimum use of data structures. –  NWS Sep 13 '11 at 11:48
It's not a good teaching example if your students can immediately think of a non-recursive solution. Why would someone pay attention when your example is "Here's something trivial to do with a loop. Now I'm going to show you a harder way for no apparent reason." –  Brendan Long Sep 13 '11 at 15:44

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.

-

A binary search algorithm sounds like what you want.

-

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)
-
• 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.
-
Whilst this may theoretically answer the question, it would be preferable to include the essential parts of those questions and answers here, and provide the links for reference. If the questions are ever removed from SO, your answer will be completely useless. –  Anna Lear Sep 13 '11 at 14:35
+1: It's been asked. –  S.Lott Sep 13 '11 at 14:38
@vemv Delete votes, moderators, rules about what's on topic changing... it can happen. Either way, having a more complete answer here would be preferable than sending a visitor to four different pages right off the bat. –  Anna Lear Sep 13 '11 at 20:57
@SF If we could close it as a duplicate, we would, but cross-site duplicates aren't supported. Programmers is a separate site, so ideally answers here would use SO as any other reference, not delegate to it entirely. It's no different than just saying "your answer is in this book" - technically true, but cannot be used right away without consulting the reference. –  Anna Lear Sep 14 '11 at 12:00

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

-

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:] )
-

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.

-

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

-

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

-
That's generally better served by a process queue as opposed to recursion in the traditional sense. –  fluffy Sep 13 '11 at 17:05

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.

-

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

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.

-

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

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)

-

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.

-