[recursion] Real-world examples of recursion

What are real-world problems where a recursive approach is the natural solution besides depth-first search (DFS)?

(I don't consider Tower of Hanoi, Fibonacci number, or factorial real-world problems. They are a bit contrived in my mind.)

Surely that many compilers out there use recursion heavily. Computer languages are inherently recursive themselves (i.e., you can embed 'if' statements inside other 'if' statements, etc.).

Since you don't seem to like computer science or mathy examples, here is a different one: wire puzzles.

Many wire puzzles involve removing a long closed loop of wire by working it in and out of wire rings. These puzzles are recursive. One of them is called "arrow dynamics". I am sue you could find it if you google for "arrow dynamics wire puzzle"

These puzzles are a lot like the towers of Hanoi.

Some great examples of recursion are found in functional programming languages. In functional programming languages (Erlang, Haskell, ML/OCaml/F#, etc.), it's very common to have any list processing use recursion.

When dealing with lists in typical imperative OOP-style languages, it's very common to see lists implemented as linked lists ([item1 -> item2 -> item3 -> item4]). However, in some functional programming languages, you find that lists themselves are implemented recursively, where the "head" of the list points to the first item in the list, and the "tail" points to a list containing the rest of the items ([item1 -> [item2 -> [item3 -> [item4 -> []]]]]). It's pretty creative in my opinion.

This handling of lists, when combined with pattern matching, is VERY powerful. Let's say I want to sum a list of numbers:

let rec Sum numbers =
    match numbers with
    | [] -> 0
    | head::tail -> head + Sum tail

This essentially says "if we were called with an empty list, return 0" (allowing us to break the recursion), else return the value of head + the value of Sum called with the remaining items (hence, our recursion).

For example, I might have a list of URLs, I think break apart all the URLs each URL links to, and then I reduce the total number of links to/from all URLs to generate "values" for a page (an approach that Google takes with PageRank and that you can find defined in the original MapReduce paper). You can do this to generate word counts in a document also. And many, many, many other things as well.

You can extend this functional pattern to any type of MapReduce code where you can taking a list of something, transforming it, and returning something else (whether another list, or some zip command on the list).

1. The College Savings Plan: Let A(n) = amount saved for college after n months A(0) = $500 Each month , $50 is deposited into an account which earns 5% in annual interest.

Then A(n) = A(n-1) + 50 + 0.05*(1/12)* A(N-1)

Suppose you are building a CMS for a website, where your pages are in a tree structure, with say the root being the home-page.

Suppose also your {user|client|customer|boss} requests that you place a breadcrumb trail on every page to show where you are in the tree.

For any given page n, you'll may want to walk up to the parent of n, and its parent, and so on, recursively to build a list of nodes back up to the root of page tree.

Of course, you're hitting the db several times per page in that example, so you may want to use some SQL aliasing where you look up page-table as a, and page-table again as b, and join a.id with b.parent so you make the database do the recursive joins. It's been a while, so my syntax is probably not helpful.

Then again, you may just want to only calculate this once and store it with the page record, only updating it if you move the page. That'd probably be more efficient.

Anyway, that's my $.02

A method to generate a tree structured menu from a database table using subsonic.

public MenuElement(BHSSiteMap node, string role)
    {
        if (CheckRole(node, role))
        {
            ParentNode = node;

            // get site map collection order by sequence
            BHSSiteMapCollection children = new BHSSiteMapCollection();

            Query q = BHSSiteMap.CreateQuery()
                    .WHERE(BHSSiteMap.Columns.Parent, Comparison.Equals, ParentNode.Id)
                    .ORDER_BY(BHSSiteMap.Columns.Sequence, "ASC");

            children.LoadAndCloseReader(q.ExecuteReader());

            if (children.Count > 0)
            {
                ChildNodes = new List<MenuElement>();

                foreach (BHSSiteMap child in children)
                {
                    MenuElement childME = new MenuElement(child, role);
                    ChildNodes.Add(childME);
                }
            }
        }
    }

Recursion is a very basic programming technique, and it lends itself to so many problems that listing them is like listing all problems that can be solved by using addition of some kind. Just going through my Lisp solutions for Project Euler, I find: a cross total function, a digit matching function, several functions for searching a space, a minimal text parser, a function splitting a number into the list of its decimal digits, a function constructing a graph, and a function traversing an input file.

The problem is that many if not most mainstream programming languages today do not have tail call optimization so that deep recursion is not feasible with them. This inadequacy means that most programmers are forced to unlearn this natural way of thinking and instead rely on other, arguably less elegant looping constructs.

You have a building. The building has 20 rooms. Legally, you can only have a certain amount of people in each room. Your job is to automatically assign people to a room. Should I room get full, you need to find an available room. Given that only certain rooms can hold certain people, you also need to be careful on which room.

For example:

Rooms 1, 2, 3 can roll in to each other. This room is for kids who can't walk on their own, so you want them away from everything else to avoid distraction and other sickness (which isn't a thing to older people, but to a 6mo it can become very bad. Should all three be full, the person must be denied entrance.

Rooms 4, 5, 6 can roll in to each other. This room is for people that are allergic to peanuts and thusly, they can not go in to other rooms (which may have stuff with peanuts). Should all three become full, offer up a warning asking their allergy level and perahsp they can be granted access.

At any given time, rooms can change. So you may allow room 7-14 be no-peanut rooms. You don't know how many rooms to check.

Or, perhaps you want to seperate based on age. Grade, gender, etc. These are just a couple examples I've come in to.

• Parsing an XML file.
• Efficient search in multi-dimensional spaces. E. g. quad-trees in 2D, oct-trees in 3D, kd-trees, etc.
• Hierarchical clustering.
• Come to think of it, traversing any hierarchical structure naturally lends itself to recursion.
• Template metaprogramming in C++, where there are no loops and recursion is the only way.

Check if the created image is going to work within a size restricted box.

function check_size($font_size, $font, $text, $width, $height) {
        if (!is_string($text)) {
            throw new Exception('Invalid type for $text');
        }   
        $box = imagettfbbox($font_size, 0, $font, $text);
        $box['width'] = abs($box[2] - $box[0]);
        if ($box[0] < -1) {
            $box['width'] = abs($box[2]) + abs($box[0]) - 1;
        }   
        $box['height'] = abs($box[7]) - abs($box[1]);
        if ($box[3] > 0) {
            $box['height'] = abs($box[7] - abs($box[1])) - 1;
        }   
        return ($box['height'] < $height && $box['width'] < $width) ? array($font_size, $box['width'], $height) : $this->check_size($font_size - 1, $font, $text, $width, $height);
    }

I have a system that uses pure tail recursion in a few places to simulate a state machine.

Anything program with tree or graph data structures will likely have some recursion.

Real world requirement I got recently:

Requirement A: Implement this feature after thoroughly understanding Requirement A.

I just wrote a recursive function to figure out if a class needed to be serialized using a DataContractSerializer. The big issue came with templates/generics where a class could contain other types that needed to be datacontract serialized... so it's go through each type, if it's not datacontractserializable check it's types.

Recursion is applied to problems (situations) where you can break it up (reduce it) into smaller parts, and each part(s) looks similar to the original problem.

Good examples of where things that contain smaller parts similar to itself are:

• tree structure (a branch is like a tree)
• lists (part of a list is still a list)
• containers (Russian dolls)
• sequences (part of a sequence looks like the next)
• groups of objects (a subgroup is a still a group of objects)

Recursion is a technique to keep breaking the problem down into smaller and smaller pieces, until one of those pieces become small enough to be a piece-of-cake. Of course, after you break them up, you then have to "stitch" the results back together in the right order to form a total solution of your original problem.

Some recursive sorting algorithms, tree-walking algorithms, map/reduce algorithms, divide-and-conquer are all examples of this technique.

In computer programming, most stack-based call-return type languages already have the capabilities built in for recursion: i.e.

• break the problem down into smaller pieces ==> call itself on a smaller subset of the original data),
• keep track on how the pieces are divided ==> call stack,
• stitch the results back ==> stack-based return

If you have two different but similar sequences and want to match the components of each sequence such that large contiguous chunks are favored first followed by identical sequence order, then you can recursively analyze those sequences to form a tree and then recursively process that tree to flatten it.

Reference: Recursion & Memoization Example Code

Parsers and compilers may be written in a recursive-descent method. Not the best way to do it, as tools like lex/yacc generate faster and more efficient parsers, but conceptually simple and easy to implement, so they remain common.

Everything where you use iteration is done more natural with recursion if it where not for the practical limitation of causing a stack overflow ;-)

But seriously Recursion and Iteration are very interchangeable you can rewrite all algorithm using recursion to use iteration and vise versa. Mathematicians like recursion and programmers like iteration. That is probably also why you see all these contrived examples you mention. I think the method of mathematical proof called Mathematical induction has something to do why mathematicians like recursion. http://en.wikipedia.org/wiki/Mathematical_induction

A "real-world" problem solved by recursion would be nesting dolls. Your function is OpenDoll().

Given a stack of them, you would recursilvey open the dolls, calling OpenDoll() if you will, until you've reached the inner-most doll.

How about anything involving a directory structure in the file system. Recursively finding files, deleting files, creating directories, etc.

Here is a Java implementation that recursively prints out the content of a directory and its sub-directories.

import java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String filePath) {

        File currentDirOrFile = new File(filePath);

        if ( !currentDirOrFile.exists() ){
            return;
        }
        else if ( currentDirOrFile.isFile() ){
            System.out.println(indentation + currentDirOrFile.getName());
            return;
        }
        else{
            System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
            indentation.append("   ");

            for ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}

Finding the median in average-case O(n). Equivalent to finding the k-th largest item in a list of n things, with k=n/2:

Here, partition picks a pivot element, and in one pass through the data, rearranges the list so that items less than the pivot come first, then the pivot, then items bigger than the pivot. The "kthLargest" algorithm is very similar to quicksort, but recurses on only one side of the list.

For me, this is the simplest recursive algorithm that runs faster than an iterative algorithm. It uses 2*n comparisons on average, regardless of k. This is much better than the naive approach of running k passes through the data, finding the minimum each time, and discarding it.

Alejo

Write a function that translates a number like 12345.67 to "twelve thousand three hundred forty-five dollars and sixty-seven cents."

Inductive reasoning, the process of concept-formation, is recursive in nature. Your brain does it all the time, in the real world.

Ditto the comment about compilers. The abstract syntax tree nodes naturally lend themselves to recursion. All recursive data structures (linked lists, trees, graphs, etc.) are also more easily handled with recursion. I do think that most of us don't get to use recursion a lot once we are out of school because of the types of real-world problems, but it's good to be aware of it as an option.

Phone and cable companies maintain a model of their wiring topology, which in effect is a large network or graph. Recursion is one way to traverse this model when you want to find all parent or all child elements.

Since recursion is expensive from a processing and memory perspective, this step is commonly only performed when the topology is changed and the result is stored in a modified pre-ordered list format.

A real world example of indirect recursion would be asking your parents if you can have that video game for christmas. Dad: "Ask mom."... Mom: "Ask Dad." [In short, "No, but we dont want to tell you that lest you throw a tantrum."]

Matt Dillard's example is good. More generally, any walking of a tree can generally be handled by recursion very easily. For instance, compiling parse trees, walking over XML or HTML, etc.

Calculations for finance/physics, such as compound averages.

Parsing a tree of controls in Windows Forms or WebForms (.NET Windows Forms / ASP.NET).

Methods for finding a square root are recursive. Useful for calculating distances in the real world.

I wrote an XML parser once that would have been much harder to write without recursion.

I suppose you can always use a stack + iteration, but sometimes recursion is just so elegant.

Recursion is appropriate whenever a problem can be solved by dividing it into sub-problems, that can use the same algorithm for solving them. Algorithms on trees and sorted lists are a natural fit. Many problems in computational geometry (and 3D games) can be solved recursively using binary space partitioning (BSP) trees, fat subdivisions, or other ways of dividing the world into sub-parts.

Recursion is also appropriate when you are trying to guarantee the correctness of an algorithm. Given a function that takes immutable inputs and returns a result that is a combination of recursive and non-recursive calls on the inputs, it's usually easy to prove the function is correct (or not) using mathematical induction. It's often intractable to do this with an iterative function or with inputs that may mutate. This can be useful when dealing with financial calculations and other applications where correctness is very important.

Multiplication of natural numbers is a real-world example of recursion:

To multiply x by y
  if x is 0
    the answer is 0
  if x is 1
    the answer is y
  otherwise
    multiply x - 1 by y, and add x

I wrote a tree in C# to handle lookups on a table that a 6-segmented key with default cases (if key[0] doesn't exist, use the default case and continue). The lookups were done recursively. I tried a dictionary of dictionaries of dictionaries (etc) and it got way too complex very quickly.

I also wrote a formula evaluator in C# that evaluated equations stored in a tree to get the evaluation order correct. Granted this is likely a case of choosing the incorrect language for the problem but it was an interesting exercise.

I didn't see many examples of what people had done but rather libraries they had used. Hopefully this gives you something to think about.

Finding the median in average-case O(n). Equivalent to finding the k-th largest item in a list of n things, with k=n/2:

Here, partition picks a pivot element, and in one pass through the data, rearranges the list so that items less than the pivot come first, then the pivot, then items bigger than the pivot. The "kthLargest" algorithm is very similar to quicksort, but recurses on only one side of the list.

For me, this is the simplest recursive algorithm that runs faster than an iterative algorithm. It uses 2*n comparisons on average, regardless of k. This is much better than the naive approach of running k passes through the data, finding the minimum each time, and discarding it.

Alejo

We use them to do SQL path-finding.

I will also say it's painstaking to debug, and it's very easy for a poor programmer to screw it up.

In my job we have a system with a generic data structure that can be described as a tree. That means that recursion is a very effective technique to work with the data.

Solving it without recursion would require a lot of unnecessary code. The problem with recursion is that it is not easy to follow what happens. You really have to concentrate when following the flow of execution. But when it works the code is elegant and effective.

Plug: http://picogen.deviantart.com/gallery/

The best example I know is quicksort, it is a lot simpler with recursion. Take a look at:

shop.oreilly.com/product/9780596510046.do

www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047

(Click on the first subtitle under the chapter 3: "The most beautiful code I ever wrote").

Recursion is used in things like BSP trees for collision detection in game development (and other similar areas).

Methods for finding prime numbers are recursive. Useful for generating hash keys, for various encryption schemes that use factors of large numbers.

Mostly recursion is very natural for dealing with recursive data structures. This basically means list structures, and tree structures. But recursion is also a nice natural way of /creating/ tree structures on the fly in some way, by divide-and-conquer for instance quicksort, or binary search.

I think your question is a bit misguided in one sense. What's not real-world about depth first search? There's a lot you can do with depth-first search.

For instance, another example I thought of giving is recursive descent compilation. It is enough of a real-world problem to have been used in many real-world compilers. But you could argue it is DFS, it is basically a depth-first-search for a valid parse tree.

Towers of Hanoi

Here's one you can interact with: http://www.mazeworks.com/hanoi/

Using recurrence relations, the exact number of moves that this solution requires can be calculated by: 2h - 1. This result is obtained by noting that steps 1 and 3 take Th - 1 moves, and step 2 takes one move, giving Th = 2Th - 1 + 1. See: http://en.wikipedia.org/wiki/Towers_of_hanoi#Recursive_solution

I think that this really depends upon the language. In some languages, Lisp for example, recursion is often the natural response to a problem (and often with languages where this is the case, the compiler is optimized to deal with recursion).

The common pattern in Lisp of performing an operation on the first element of a list and then calling the function on the rest of the list in order to either accumulate a value or a new list is quite elegant and most natural way to do a lot of things in that language. In Java, not so much.

Feedback loops in a hierarchical organization.

Top boss tells top executives to collect feedback from everyone in the company.

Each executive gathers his/her direct reports and tells them to gather feedback from their direct reports.

And on down the line.

People with no direct reports -- the leaf nodes in the tree -- give their feedback.

The feedback travels back up the tree with each manager adding his/her own feedback.

Eventually all the feedback makes it back up to the top boss.

This is the natural solution because the recursive method allows filtering at each level -- the collating of duplicates and the removal of offensive feedback. The top boss could send a global email and have each employee report feedback directly back to him/her, but there are the "you can't handle the truth" and the "you're fired" problems, so recursion works best here.

Disabling/setting read-only for all children controls in a container control. I needed to do this because some of the children controls were containers themselves.

public static void SetReadOnly(Control ctrl, bool readOnly)
{
    //set the control read only
    SetControlReadOnly(ctrl, readOnly);

    if (ctrl.Controls != null && ctrl.Controls.Count > 0)
    {
        //recursively loop through all child controls
        foreach (Control c in ctrl.Controls)
            SetReadOnly(c, readOnly);
    }
}

People often sort stacks of documents using a recursive method. For example, imagine you are sorting 100 documents with names on them. First place documents into piles by the first letter, then sort each pile.

Looking up words in the dictionary is often performed by a binary-search-like technique, which is recursive.

In organizations, bosses often give commands to department heads, who in turn give commands to managers, and so on.

A real world example of recursion

Recursion is often used in implementations of the Backtracking algorithm. For a "real-world" application of this, how about a Sudoku solver?

Everything where you use iteration is done more natural with recursion if it where not for the practical limitation of causing a stack overflow ;-)

But seriously Recursion and Iteration are very interchangeable you can rewrite all algorithm using recursion to use iteration and vise versa. Mathematicians like recursion and programmers like iteration. That is probably also why you see all these contrived examples you mention. I think the method of mathematical proof called Mathematical induction has something to do why mathematicians like recursion. http://en.wikipedia.org/wiki/Mathematical_induction

Famous Eval/Apply cycle from SICP

_{(source: mit.edu)}

Here is the definition of eval:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type - EVAL" exp))))

Here is the definition of apply:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type - APPLY" procedure))))

Here is the definition of eval-sequence:

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

eval -> apply -> eval-sequence -> eval

You have an organization tree that is N levels deep. Several of the nodes are checked, and you want to expand out to only those nodes that have been checked.

This is something that I actually coded. Its nice and easy with recursion.

XML, or traversing anything that is a tree. Although, to be honest, I pretty much never use recursion in my job.

The last real world example I have is a pretty frivolous, but it demonstrates how recursion 'just fits' sometimes.

I was using the Chain of Responsibility pattern,so a Handler object either handles a request itself, or delegates it down the chain. It's useful to log the construction of the chain:

public String getChainString() {
    cs = this.getClass().toString();
    if(this.delegate != null) {
        cs += "->" + delegate.getChainString();
    }
    return cs;
}

You could argue that this isn't the purest recursion, because although the method calls "itself", it is in a different instance each time it's called.

Geometric calculations for GIS or cartography, such as finding the edge of a circle.

Quicksort, merge sort, and most other N-log N sorts.

Recursion is a very basic programming technique, and it lends itself to so many problems that listing them is like listing all problems that can be solved by using addition of some kind. Just going through my Lisp solutions for Project Euler, I find: a cross total function, a digit matching function, several functions for searching a space, a minimal text parser, a function splitting a number into the list of its decimal digits, a function constructing a graph, and a function traversing an input file.

The problem is that many if not most mainstream programming languages today do not have tail call optimization so that deep recursion is not feasible with them. This inadequacy means that most programmers are forced to unlearn this natural way of thinking and instead rely on other, arguably less elegant looping constructs.