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.

• While your question is completely valid, I'd hesitate calling Fibonacci numbers useless in real life. Same goes for factorial. Sep 13, 2011 at 13:48
• The Little Schemer is a whole book on recursion that never uses Fact or Fib. junix-linux-config.googlecode.com/files/… Sep 13, 2011 at 13:49
• @Zach: Even so, recursion is a horrible way to implement Fibonacci numbers, because of the exponential running time. Sep 13, 2011 at 18:05
• @dan04: Recursion is a horrible way to implement almost anything due to the possibility of stack overflow in most lanaguages. Sep 14, 2011 at 12:47
• @dan04 unless your language is smart enough to implement tail call optimization like most functional languages in which case it works just fine Apr 5, 2012 at 12:29

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)
{
}

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. Sep 13, 2011 at 11:20
• Note : unix command often unclude the -r option (cp or rm for exemple). -r stand for recursive. Sep 13, 2011 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, 2011 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. Sep 14, 2011 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, 2011 at 12:57

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.

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

• Of course it should be noted that whenever you have the liberty to design your own tree structure, it's almost always better to keep pointers/references to parent/next sibling/etc. in the nodes so that you can iterate over the tree without recursion. Sep 14, 2011 at 12:50
• What do pointers have to do with it? Even when you have pointers to first child, next sibling and parent, you still have to walk through your tree somehow, and in some cases, recursion is the most feasible way. Sep 14, 2011 at 15:24
• modelling a contagious infection
• generating geometry
• directory management
• sorting

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

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

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

• BST search
• Towers of Hanoi
• palindrome search

https://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. Sep 13, 2011 at 14:35
• @Anna Well, users can't their delete their questions so how likely is that to happen? Sep 13, 2011 at 20:25
• @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. Sep 13, 2011 at 20:57
• @Anna: Following this line of thinking, every question closed as "exact duplicate" should have the answer from the original pasted in. This question IS an exact duplicate (of the questions on SO), why should it receive a different treatment than exact duplicates of questions on Programmers?
– SF.
Sep 14, 2011 at 7:30
• @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. Sep 14, 2011 at 12:00

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)

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. Sep 13, 2011 at 17:03
• Depending on what language you are using the code may or may not be explicitly recursive or imperative or recursive. But it is still a recursive algorithm in that you are breaking the problem into smaller and smaller chunks to get to the solution. Sep 14, 2011 at 3:32
• @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. Sep 14, 2011 at 12:52

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

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.) Sep 13, 2011 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. Sep 13, 2011 at 11:15
• Agreed, but OP Specifically asked for Teaching examples with minimum use of data structures.
– NWS
Sep 13, 2011 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." Sep 13, 2011 at 15:44

A binary search algorithm sounds like what you want.

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.

• you would deserve more points than just +1 from me. F# without recursion would be very tedious, this is even more true for Haskell that has no looping constructs ONLY recursion! Sep 13, 2011 at 19:44

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

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.

• A bill of Materials may be a directed grath rather then a tree, e.g. the same spec of screw can be used by more then one component.
– Ian
Sep 15, 2011 at 10:37

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);
• which language is this code written in? Nov 9, 2015 at 4:06
• @törzsmókus No specific language. The syntax is pretty close to C, Obj-C, C++, Java, and many other languages, but if you want real code you may need to substitute an appropriate operator such as || for the OR. Nov 9, 2015 at 13:03

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.

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. Sep 13, 2011 at 17:05

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: