1395

37
+10  Q:

## How did you practically use recursion?

How did you practically use recursion? I mean practical problems you had to solve in day to day programming, be that for work or for pleasure. Not school tasks/homeworks but something you did for yourself or others. The ones where I used it myself are:

• drawing some fractals
• traversing directory tree to search for a file
• traversing the DOM tree of a HTML form, which corresponded to the tree structure of the data collected and could adapt to changing form of the structure on the fly.
• nasty fork bomb that grew its own subdirectory tree infinitely on top of forking.

Specifically, I mean first-hand experiences, not thought up examples.

+2  A:

When I was developing online handwritten text recognizer I used recursion for Elastic algorithm (and yes, it's not a homework, it was a real project).

Another example: LinesCounter - program that counts lines of code of the project.

In general case you'll find recursion useful everywhere where hierarchical data structures occure.
+11  A:

I've used it on numerous projects for parsing language constructs. Recursive decent parsers are quite easy to write and map well to the structure of most languages.

+4  A:

Used it in a scenegraph-based rendering engine to traverse the graph representing my scene hierarchy and visit its nodes for different purposes (i.e. culling, collecting rendering jobs, ...).

Recursion occurs pretty much everywhere where hierarchical structures need to be represented, traversed, modified, whatever. There are countless examples.

+5  A:

This is me practically using recursion:

``````int largest = findLargestInt(intArray, 0, 0);

private int findLargestInt(int[] input, int largest, int start) {
for(int i : input)
if(i > largest) largest = i;

return largest;

if (start == ints.length) return largest;
return findLargestInt(ints, Math.max(ints[start], largest), start + 1);

}
``````
This code makes no sense at all to me...
At least there's no recursion in here ... `return largest;` doesn't seem to be calling the function itself again :-)
AAAAARRRRRRRRGHHH!!! I'm BLIND!!!What a way to get the largest number in an array!
Yeah, it's probably easier just to loop through the array keeping track of the highest number found so far...
Paulo - you don't think a for loop and returning the largest is a good way to do it? Andrew thinks so, although he didn't see that that's actually what the code's doing. It was a just a joke; it's *practically* using recursion. Just not quite.
Haha, upvoted for the incredibly dry nerdy joke in there. Anyone who doesn't see it simply isn't worthy.
@Robert Grant: Maybe putting 'practically' in italics/quotes might help more people getting the joke. +1.
Thanks guys, I'd initially thought the code was self-documenting :)
Remind me to stick a smiley on my comment next time :)
+3  A:

Recursion is very technique but you should be aware how to implement it right.

Examples:

• Traversing every file in a parent folder and going down to unknown level of subfolders.
• Traverse every element in an HTML page with unknown level of depth.
+1  A:

I used it for an organization tree where I needed to get and display information about employees and their subordinates. I guess it's very similar to traversing through file directories, just a different business context.

+10  A:

Anything that involves traversing trees. For instance, I had to get a list of all folder/sub-folders within a given folder in Business Objects (a reporting server), and I used recursion to build up this list, using output parameters (in C#), starting at the root node and recursively called the same method for all sub-folders.

A:

I have built a report generator and I used recursion for the (complex) groupings and the calculations.
The structure for holding the data was a tree.
(ie, the sums were bubbling up)

+8  A:

I think almost all the code I've ever written used recursion at some point. This question is a bit like asking "how did you practically use functions".

I don't think so. You might have used it indirectly - in the compiler, in placing the program in a directory tree etc. But how often did you write a recursive function? Over 2 years of web developer job I didn't find need for recursion even once. Currently working in embedded, I don't use even one recursive function in tens of thousands of lines of code.
I write recursive functions all the time. But then I'm not a web developer.
+1 I have to agree with you Neil. Although you say that SF, chances are there was a situation where you at least *could* have used recursion.
@Kyle: Oh, not once! But usually the solution would be more wasteful on resources, slower, and sometimes less readable. In web development there were very few opportunities. I recall actually once I did use it in building some menu tree, but that was one separated example. In the embedded I was about to choose recursion with linked lists several times, but opted for iteration and static buffers instead simply because of overhead. The situations where iteration and recurrence are almost equivalent are very common, the situations where recurrence is essential are quite rare.
@SF Recursion is often the most intuitive way to solve many problems. It may be that they are horribly inefficient, but the optimization comes later.
@SF Recursion is NEVER essential, you can always manually create a stack (and this is often more efficient as it doesn't have the overhead of function calls). Recursion is just a more natural way to present many algorithms.
While this answer is true, it doesn't really help...
If you use stack for purpose of storing state across iterations of the same variable, this is pretty much recursion except non-explicite. I once used a language with no local variables, and recurrence was achieved by calling function(params,depth){semi_local_var[depth]... }In Embedded, I can't afford the comfort of "optimizing later".
A:

Recursion is one of those techniques that you don't use much in the real world, but when you do it comes in really handy. The last time I used it was for a mortgage application for a major financial institution to help calculate some things within the XML data for the home loan.

I think most "real-world" things that aren't pure linear scripts that I've written involve recursion and/or graph traversal of some sort. So, in my experience, it's one of those techniques that you use a lot in the real world.
A:

I use it for example in .NET in my derived PropertyDescriptor class to support declarative property path syntax for data binding (á la `myGridColumn.Binding = "myDanubeSteamBoat.Captain.Hat"`). The `PropertyDescriptor` instance has to look up the parent instance in that case and so on.

Now, for Silverlight/WPF, there is a new `PropertyPath` functionality built-in for data binding, so these workarounds are not necessary n.e. moar.

+1  A:

I use it all the time to build nested `<ul>` lists for website navigation, similar to traversing directory structure, but for things like product categories / products in a database. Fun :)

+4  A:

How didn't I use recursion, you might ask?

• Traversing list- or tree-like data structures: e.g. filesystem, parse trees, employee-manager type data, LINQ like functions on `IEnumerable<T>` in C#, etc.

• Solving maze like problems: e.g. an actual maze for a little game, a percolation simulation application, etc.

• Implementing business logic that is defined recursively, like:

1. an `AddItem(Item item,DateRange range)` method on an `ItemCollection` that updates the collection in a certain way without creating overlapping date ranges in it,
2. a business rule that states that when adding an item to the collection of type `foo` an item of type `bar` needs to be added for the same date range if there is no `bar` in the collection already, and
3. implementing this with the simple line `if (item.Type == ItemType.Foo && !this.ContainsType(ItemType.Bar)) AddItem(new Item(item, ItemType.Bar), range);` inside the body of `AddItem()`.

Recursion is not magical or scary, but a tool every developer should know, be able to put to use and be able to determine when one should use it (and what the potential pitfalls are).

+1  A:

Very recently I was using recursion in PROLOG to do just about anything...

+1  A:

The last piece of code I wrote that uses recursion (both self calls and other types of functions-calling-functions) is some code to parse GCA data and character files, with the eventual aim to be able to read data and character files and to write character files.

Prior to that, it was some code to find roots of polynomials (and, based on that, Newton-Raphson fractal rendering).

+2  A:

If I program in Scheme I always use (tail-)recursion. Small functions calling many other functions is the way that I like to work in Scheme. Functions calling themselves is just a special case. No need for explicit iteration.

I find it strange that someone can program non-trivial stuff without using recursion. Recursion is something that comes very natural for me. The divide-and-conquer nature of recursion tackles the complexity of many problems quite adequately.

Tail-recursion in Scheme doesn't push the stack; that's how you can get away with all this. So the language will play a role when you ask someone if they used recursion or not.

Any recursive algorithm can be implemented iteratively, not all iterative algorithms can be implemented recursively.
@Robert Fraser: Last time I checked, algorithms were formalized exactly as the partial recursive functions.
@Robert Interesting. Which ones exactly?
Out of curiosity I turned it into a toplevel question: http://stackoverflow.com/questions/2093618/can-all-iterative-algorithms-be-expressed-recursively
A:

Putting aside functional languages, in which recursion is the norm and iterative methods are a rarity - I think the most important aspect of actually using recursion is for code readability.

Many a time I find myself considering two solutions for a specific problem, one iterative and one recursive. Depends on the case, obviously, but the major decision between an iterative and a recursive method will first and foremost be code readability.

If that specific method is mission-critical, a performance analysis will come into play. But the main issue will be which code is more short, simple and easy to comprehend.

+3  A:

I had to implement Expression Tree Visitor which have recursive behavior in order to be able to convert boolean lambda expressions into SQL WHERE clause statements.

A:

I think other answers have touched on this, but you would often use recursion in functional programming. A feature of a pure functional language is that variables are imutable (so you can't have a loop counter), so the only way to "loop" is to use recursion.

+54  A:

Duplicate of this question

Yeah, very funny.
I am ashamed of myself, it was very childish, but I couldn't resist
It's hard to visualize a question about recursion without an answer like this.
+1 A question on recursion that is itself recursive...love it!
+1 Hahaha, must say I found the funny in this :P
I clicked this twice before getting the joke.
Very helpful. A++++ Would vote again.
+1  A:

I recently used recursion for distributing a sum from the corner cell of a multidimensional OLAP cube (a hypercube really since it would have up to about 6 dimensions). In other words, I was doing the opposite of a rollup by using a desired sum and disaggregating it throughout the hypercube. The disaggregation algorithm was passed through the recursion calls as a functor.

A:

Apart from "non-real-world" (whatever that means) code, here are several times that I can think of when I had occasion to use recursion:

1. A recursive descent parser for a mini-language
2. Numerous times when I needed to traverse a tree/tree-like data structure (file systems, certain GUI widgets etc.)
3. A few times when I had to model a problem as a graph and run a recursive DFS (small online friend lists, flood-fill on an image etc.)

I'm not really sure how you define 'practical', does using recursion in solving programming problems from sites such as SPOJ and TopCoder count?

+1  A:

For basically anything with a parent-child relationship. Any kind of tree, be it directory, menu structure or organizing any other hierarchical taxonomy.

A:

Several others have pointed out tree traversal as a use of recursion. I think this deserves a bit of clarification. Recursion is useful when you need to do depth-first traversal of a tree. If you need to do breadth-first traversal, recursion is rarely (if ever) useful.

For one example of using breadth-first traversal, consider the directory structures some have mentioned. At least IMO, when you're traversing a directory structure, breadth-first traversal is generally preferred. In particular, if you do a depth-first traversal you get your results in a nearly random order, with files from one directory almost randomly interspersed with files from directories below that in the tree. A breadth-first traversal using something like a priority queue (with the priority based on file names sorting order) gives results in a much more coherent order, with all the files from the current directory followed by all the files of one subdirectory, all the files of another subdirectory, and so on (with the subdirectories sorted in the order you gave for the priority queue).

Of course, you can use depth-first traversal and still get "coherent" results -- you just have to accumulate the results and sort them before display. While this certainly works, I personally prefer to generate the results neatly, rather than generate them messily and clean up the mess afterward.

+1  A:

Recursion, as opposed to looping, is useful when you want to preserve state across iterations that would otherwise require a second stack. In these cases, recursion can be much conceptually simpler and much more readable. A good example is quick sort. (Please, no comments about how this implementation sucks. I know that already. It's meant to be illustrative, not production quality.)

``````def quickSort(array):
if len(array) < 2:
return
midPoint = partition(array)  # Partition array in place
quickSort(array[0:midPoint])
quickSort(array[midPoint:len(array)])
``````

In this case, you need to keep track of where the boundaries of each slice are. This is a lot easier if you use recursion. If you use iteration, you would have to keep track of this information explicitly.

Oh, I know -what- recursion is, and everyone has written some Quicksort, Menu tree or traversal of some nested structure sometime. It's original practical uses that interested me. Things like calculating light reflections or an employee hierarchy analysis.
+9  A:
Recursion in ray-tracking... for so many years I wondered how these clever algorithms work, and now it's so obvious. Light reflections from multiple surfaces really seems like the ultimate example of beauty of recursion.
Please vote this response up - much more sensible than mine.
Yeah, +1 for Gordon's reason. Although I voted for his too :)
+1  A:

I used it to print a list of items and sub-items with parents.

``````1. Master Task A
``````

Where all are stored in a table with a "ParentID" and "TaskID", and there is virtually no depth limit. Going through it recurcively to print them (and query for related info such as time and cost) made sense.

+1  A:

At a company that made websites for mutual fund companies, the calculation for performance was a calculation that was basically a function of the previous day's value. Different funds used slightly different formulas.

A:

Once an in-house program we had to use was so hard to use, we actually decided to read the .xml project file it produced (the recursive part) and modify it rather than use the program.

A:

I have done this for tree menu system - embedded device GUI where "clicking item" get submenu or function. It is defined that way that menus are arrays of pointers on either display_menu function or functions that does something.

Does this count as recursion?

+2  A:

Compiler writing involves lots of recursive algorithms.

A:

being very concious of the stack, i tend to avoid recursion in favour of iteration.

A:

Errmm, I would have to say, using Scheme. There is no other way!

A:

I sometimes think I use recursion too much in my job-work.

Course there is the common recursive bit for a scripting engine I wrote for my job.(recursive for both expression evalution and function calling)

And there is another recursive bit with having a form of data contain other forms of data, where the back end processes it with recursion for saving and loading...

Reallly I sometimes think I use too much recursion to not be programming in a functional/tail-recursionable language... Like once I had to write an assembly routine to generate a huge amount of permutations. The obvious approach was recursion, well I could only use a 64k stack, so I had to figure out how to write it with iteration..

A:

If Invoke is required on a function that mods a gui. I use Invoke and recall the function.

`````` public void UpdateForm()
{
if(Form.InvokeRequired)
{
Form.Invoke(new VoidNoArgDelegeta(UpateForm));
}
Form.Text = "Updated";
}
``````
A:

Here's a (sort of weird) method I wrote to take a variable number of inputs, some of which might be of type `T`, some of which might be `IEnumerable<T>`, some of which might be `IEnumerable<IEnumerable<T>>` and so on -- the method "flattens" them all out into a single `IEnumerable<T>`:

``````public static IEnumerable<T> Extract<T>(IEnumerable objects) {
foreach (object obj in objects) {
if (obj is T) {
T nextItem = (T)obj;
yield return nextItem;

} else if (obj is IEnumerable) {
IEnumerable nextItems = obj as IEnumerable;
foreach (T item in Extract(nextItems))
yield return item;
}
}

yield break;
}

public static IEnumerable<T> Extract<T>(params object[] objects) {
return Extract<T>(objects as IEnumerable);
}
``````

The original idea was to be able to put together a few different `List<T>` objects into a single list very quickly via something like:

``````List<string> allSymbols =
new List<string>(ExtractSymbols(aSymbols, bSymbols, cSymbols));
``````

But, as developers sometimes do, I was seduced by the idea of making it generic and so `ExtractSymbols` became simply `Extract<T>`. (In retrospect it probably should've been called `Flatten<T>`).

A:

Copying directory structures

the problem is

My recursions sometimes result in a STACK OVERFLOW error. :)