Real-world examples of recursion

Question

Can anyone suggest real-world problems where a recursive approach is the natural solution besides DFS?

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

Answer 1

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

Answer 2

Quick sort, merge sort, and most other N-logN sorts

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

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.

Answer 15

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 Quick-sort, 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.

Answer 16

We use them to do SQL path-finding.

I will also say it's a pain-in-the-ass to debug, and it's very easy for a poor programmer to screw it up.

Answer 17

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."]

Answer 18

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.

Answer 19

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

Answer 20

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

Answer 21

Recursion is appropriate whenever a problem can be solved by dividing it into sub-problems. Algorithms on trees and sorted lists are a natural fit. Many problems in computational geometry (and 3d games) can be solved recursively using 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.

Answer 22

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.

Answer 23

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.

Answer 24

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.

Answer 25

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.

Answer 26

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

Answer 27

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.

Answer 28

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

Answer 29

Real world requirement I got recently:

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

Answer 30

Calculations for finance/physics, such as compound averages.

Answer 31

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

Answer 32

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

Answer 33

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

Answer 34

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.

Answer 35

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

http://oreilly.com/catalog/9780596510046/toc.html (Click on the first subtitle under the chapter 3: "The most beautiful code I ever wrote").

Answer 36

There are lots of mathy examples here, but you wanted a real world example, so with a bit of thinking, this is possibly the best I can offer:

You find a person who has contracted a given contageous infection, which is non fatal, and fixes itself quickly( Type A) , Except for one in 5 people ( We'll call these type B ) who become permanently infected with it and shows no symptoms and merely acts a spreader.

This creates quite annoying waves of havoc when ever type B infects a multitude of type A.

Your task is to track down all the type Bs and immunise them to stop the backbone of the disease. Unfortunately tho, you cant administer a nationwide cure to all, because the people whom are typeAs are also deadly allergic to the cure that works for type B.

The way you would do this, would be social discovery, given an infected person(Type A), choose all their contacts in the last week, marking each contact on a heap. When you test a person is infected, add them to the "follow up" queue. When a person is a type B, add them to the "follow up" at the head ( because you want to stop this fast ).

After processing a given person, select the person from the front of the queue and apply immunization if needed. Get all their contacts previously unvisited, and then test to see if they're infected.

Repeat until the queue of infected people becomes 0, and then wait for another outbreak..

( Ok, this is a bit iterative, but its an iterative way of solving a recursive problem, in this case, breadth first traversal of a population base trying to discover likely paths to problems, and besides, iterative solutions are often faster and more effective, and I compulsively remove recursion everywhere so much its become instinctive. .... dammit! )

Answer 37

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

Answer 38

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

Answer 39

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

Answer 40

You can use it for this kind of thing (untested):

void BuildStackFromException(Exception e, ref ErrorStack stack)
{
   if (e == null)
       throw new ArgumentNullException("e");

   if (e.InnerException != null)
       BuildStackFromException(e.InnerException, ref stack);

   stack.Push(e.Message);
}

Answer 41

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

Answer 42

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.

Answer 43

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 FP 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 Page Rank 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).

Answer 44

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.

Answer 45

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

Answer 46

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:

int kthLargest(list, k, first, last) { j = partition(list, first, last) if (k == j) return list[j] else if (k

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

Answer 47

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.

Answer 48

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

Answer 49

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