How did you practically use recursion?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

}

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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)

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

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.

Answer 17

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.

Answer 18

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.

Answer 19

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.

Answer 20

Duplicate of this question

Answer 21

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.

Answer 22

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?

Answer 23

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

Answer 24

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.

Answer 25

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.

Answer 26

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

Picture a list of tasks and sub-tasks:

1. Master Task A
1.1 SubTask A
1.2 SubTask B
1.2.1 SubTask C
1.2.2 SubTask D
1.2.2.1 SubTask E
2. Master Task B

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.

Answer 27

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.

Answer 28

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.

Answer 29

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?

Answer 30

Compiler writing involves lots of recursive algorithms.

Answer 31

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

Answer 32

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

Answer 33

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

Answer 34

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

Answer 35

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

Answer 36

Copying directory structures

the problem is

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