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

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

+43
A:

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

Matt Dillard
2008-09-19 21:37:12

A file system provides motivation (which is good, thanks) but this is a specific example of DFS.

redfood
2008-09-19 21:46:12
I didn't get the acronym "DFS" - it's been awhile since I sat in a classroom.

Matt Dillard
2008-09-19 21:48:50
depth-first search: dfs( node ){ foreach child in node{ visit( child );}}

Haoest
2008-09-20 08:56:48
For simple code example, see e.g. http://stackoverflow.com/questions/126756/examples-of-recursive-functions/2765589#2765589

Jonik
2010-05-06 18:57:19
+6
A:

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

Mark
2008-09-19 21:38:06

+11
A:

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.

Cody Brocious
2008-09-19 21:38:26

A:

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.

Steve Moyer
2008-09-19 21:38:52

+3
A:

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

Charles Graham
2008-09-19 21:39:32

I used recursion once in my career, and when the framework changed, I got rid of it. 80% of what we do is CRUD.

Charles Graham
2008-09-20 00:07:31
+6
A:

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

Martin Cote
2008-09-19 21:40:10

John, the fact that you can nest if statements means that the language definition (and likely the language parser) is recursive.

Derek Park
2008-09-19 22:27:19
Recursive descent is one of the easiest ways to hand-code a compiler. Not as easy as using a tool like yacc, but easier to understand how it works. The whole table-driven state machines can be explained, but usually end up being black boxes.

Eclipse
2008-10-09 19:53:50
A:

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.

Stephen Wrighton
2008-09-19 21:43:30

+10
A:

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

bkane
2008-09-19 21:43:47

A:

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

Apocalisp
2008-09-19 21:44:09

+2
A:

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.

Dima
2008-09-19 21:44:14

+2
A:

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

Sam McAfee
2008-09-19 21:44:20

+2
A:

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.

MagicKat
2008-09-19 21:44:31

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.

Telos
2008-09-19 21:45:05

A:

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.

A:

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

Mostlyharmless
2008-09-19 21:46:36

static void Main(string[] args) { AskDaddy(); }static void AskDaddy() { AskMommy(); }static void AskMommy() { AskDaddy(); }This is a stack overflow. NOT RECURSION.

Paul Batum
2008-09-19 21:59:45
@ Paul Batum: Thats EXACTLY their strategy. Also, if you recurse deep enough, you are bound to overflow even if there is a termination condition. You just need to make it deep enough that it will terminate AFTER the overflow point.

Mostlyharmless
2008-09-19 22:02:38
+2
A:

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.

davenpcj
2008-09-19 21:46:40

A:

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

shogun
2008-09-19 21:48:44

+3
A:

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

BCS
2008-09-19 21:51:11

Of course it's code you insensitive clod! Raytracing or geometric definitioan can be solved by doing recursion, not that it _has_ to be, but it is one way.

Mats Fredriksson
2008-09-19 22:28:28
+7
A:

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.

Sam
2008-09-19 21:51:21

A:

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.

origin
2008-09-19 21:52:18

+2
A:

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.

Tommy
2008-09-19 21:54:12

A:

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.

Paul Wicks
2008-09-19 21:54:56

+4
A:

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.

tkerwin
2008-09-19 21:56:43

+6
A:

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

chitza
2008-09-19 21:56:46

A:

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.

Austin Salonen
2008-09-19 22:00:20

A:

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

Apocalisp
2008-09-19 22:03:28

A:

Real world requirement I got recently:

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

dragon
2008-09-19 22:14:03

A:

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

Apocalisp
2008-09-19 22:15:05

A:

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

Apocalisp
2008-09-19 22:15:45

A:

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

Apocalisp
2008-09-19 22:19:00

A:

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.

Nazadus
2008-09-19 22:22:01

+2
A:

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

Fabio Ceconello
2008-09-19 22:22:54

+10
A:

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

Kent Fredric
2008-09-19 22:25:42

Thanks - this is still graph traversal but it is well motivated and makes sense to non-programmers people.

redfood
2008-09-23 03:49:07
A:

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

Mark Harrison
2008-09-19 22:39:37

A:

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

mk
2008-09-19 23:57:54

A:

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

Robert Rossney
2008-09-20 00:03:52

A:

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

ilitirit
2008-09-20 01:29:52

A:

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

JPrescottSanders
2008-09-20 02:20:20

A:

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.

dicroce
2008-09-20 03:21:25

+3
A:

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

jolson
2008-09-20 04:07:32

A:

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.

slim
2008-09-20 04:29:29

+2
A:

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

Andrei Rinea
2008-09-20 09:28:06

A:

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 (kHere, `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

A:

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.

Svante
2008-11-16 00:51:28

A:

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:

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

Noctis Skytower
2010-07-27 04:15:24