The Old Joel on Software Forum: Part 4 (of 5) - The last time you used recursion at work

The last time you used recursion at work

This recursion thread was met with quite some enthusiasm, so I thought I'd ask: What is the last example (or 2) of when you used recursion to write an algorithm at work? Feel free to post a code sample. Maybe we can compile a nice "real world intro to recursion" article from the submissions

Bella
Thursday, May 20, 2004

Never. But then again I'm a self-taught coder, so I might have been doing something the hard way.

Pietro
Thursday, May 20, 2004

Who will be the first to reply to this and make their reply recursive?

Ross
Thursday, May 20, 2004

(Sort of) Second Pietro's comment. Built my own equation editor and had to use recursion to reconcile BODMAS. And then I discovered MS's Script Control! Doh! This was about a year ago.

KayJay
Thursday, May 20, 2004

Its been a while. I think the last one was a middle tier server in perl that had one recursive routine for parsing command input strings.

Before that, (when life was simpler, and operating systems simpler still), I wrote a single disk copier (copied into memory, swap disk, write out, swap disk read next set of files, fill memory, etc).

And at about the same I implemented the flood fill in DR Logo using recursion, but then had to unwind and use a loop method instead because Logo's stack blew up on large areas.

Simon Lucy
Thursday, May 20, 2004

While it wasn't at "work", I did use recursion to go through folders and opening them and counting the lines in them, to give me a rough estimate of how many LOC I have (I realise LOC is different to Lines, but I doubt it was tooo far off).

Nerdo
Thursday, May 20, 2004

Last week. Populating a Treeview control representing a folder-like structure pulled from a database.

GiorgioG
Thursday, May 20, 2004

Recursive building of a filelist in a nested directory structure.

Memory use wasn't an issue, so it was the easiest way to walk a directory structure. Actually, I've done the same trick more than once.. That's probably my one exception to the rule of never using recursion in production code.

deja vu
Thursday, May 20, 2004

I manage a yellow pages search web site. If you search for a business in an area and no results are found, we automatically search a larger area. Under the covers, the main search method calls itself recursively until we get some results. I did feel the need to put a big "recursive call - watch out!" comment in there though.

Mark B
Thursday, May 20, 2004

Anytime you need to go through a tree type data structure recursion comes into play. So most of use will probably use recursion quite often. Although many won't realize it as they use a standard FindAllFiles(Files, RootFolder, IncludeSubDirectories) method.

As a real world example: let them get the total file count on their harddisk using recursion.

Jan Derk
Thursday, May 20, 2004

I have an n-level xml-based navigation structure that is parsed recursively using XSLT. I tried doing it in vb/asp, but alas, not a good idea.

On the server backend, I use a few recursive scripts to clean up temporary files and the like. They're in Java.... I know those should be in perl, but I've been staying away from it on purpose.

KC
Thursday, May 20, 2004

Gee... Now that I think over it I've never used it in real world work situations.

Last time I used it (scratching my head) about 5 years back in academics to traverse a binary tree in post, pre, in order form. Before that I did use it for Towers of Hanoi, Knight's problem, quick sort and the like...

The One You Loved (TOYL)
Thursday, May 20, 2004

A couple of weeks ago, I am creating an application config which is nested. The user can configure groups of actions, an individual action could be another group. It doesn't come up very often but is one of those important things a programmer should know.

Tony Edgecombe
Thursday, May 20, 2004

I use recursion to build, and compact, encoding trees.

Mr Jack
Thursday, May 20, 2004

I use recursion a lot, but with object orientation, it's not explicit. i.e., I build some treeNode object which checks its children. My code doesn't LOOK recursive, but it is.

anon
Thursday, May 20, 2004

Last week I wrote a recursive template in XSLT to do some bitwise stuff. Wacky fun.

Thom Lawrence
Thursday, May 20, 2004

We use it to build products in our product.

Basically a customer can order a bathroom suite, the system realises it needs to order taps, a bath, toilet, sink etc. The bath might be made from the main bath and two side panels.

This can be taken to as much detail as is required by end users.

Steven
Thursday, May 20, 2004

Years ago. Wrote a solver for Rubik's Tangle. Work related? Well, it took less time than solving it by hand, so I got back to work sooner...

Paul Sharples
Thursday, May 20, 2004

I usese recrusion all the time. Usually, it involves a BOM (Bill Of Materials) type structure. You've got some product, that is manufactured and it's made up of sub assemblies bolted together at the plant. The sub assemblies may themselves be made of sub assemblies, and those may be made of smaller sub assemblies, continue ... (recursively) ... until you get down to the basic part that is a single entity.

This, in our world (bits and bytes), translates to a standard tree type structure that is simply begging for recursion.

Recursion makes handling the tree structures very straight forward and clean. Wouldn't want to do it without recursion.

Sgt. Sausage
Thursday, May 20, 2004

Had to implement QuickSort which is recursive in nature.

BobRoss
Thursday, May 20, 2004

Not that long ago.

It was to do with working out coordinates for laying out information on a PDF, where positions could be relative to one another, and 'inherit' their parents position if the parent contained no data to be printed....

Gordon Hartley
Thursday, May 20, 2004

The last time: a component to search a directory tree for CAD drawing files based on a tool number.

The most fun: a recursive descent parser for a mini-language based on VB's FRM file format. I used it for a report designer I developed (a long time ago) and have used it since to write tools to safely search through VB source files for specific components, properties, etc.

Craig
Thursday, May 20, 2004

Actually, Java compiles in a recursive way. By default it will compile exactly what you tell it to compile.

If that has dependencies that are not compiled, it will do those.

If those have dependencies that are not compiled, it will do those.

Lather, rinse, repeat.

KC
Thursday, May 20, 2004

I use recursion for parsing XML.

The Real PC
Thursday, May 20, 2004

It was when I implemented a TreeView control. For example:

void TreeView::ItemExpand(TreeView::Item item)
{
//expand this item's children
foreach (TreeView::Item child_item in item.children)
{
//recurse
ItemExpand(child_item);
}
//expand this item
item.expanded = true;
}

Christopher Wells
Thursday, May 20, 2004

Last time I used recursion at work was in designing the data transfer mechanism for an embedded real-time system. This simplified the code for moving variable-length data from one SMB to another.

Some might balk at the use of recursion in a real-time system, but data movement lends itself to a tail-recursive algorithm, which optimizing compilers really like. Additionally, the nature of the data is such that the recursion is never more than one level deep.

I guess the moral of this story is that recursion can be useful even in unexpected places, provided that the implications of using it are well understood.

For interested parties, the code looks a little something like this (various bits have been changed to protect proprietary code):

void Send(byte* bytes, int len) {
//Check recursion base-case
if(len <= 0){
if(len < 0){
//Error condition
}
return;
}
//Determine how much to copy
int copySize = (len <= (data.getMaxElemSize() - outLevel) ?
len : (data.getMaxElemSize() - outLevel));

//Retrieve a starting index to copy into
byte* outPtr = data[outLevel];
if(outPtr == 0){
//Error condition
}

//Perform the copy and update current outLevel
memcpy(outPtr, bytes, copySize);
outLevel += copySize;

//Make the current buffer available if it's full
if(outLevel == data.getMaxElemSize()){
//Do a transfer to get some free space
}

//Copy anything that's left in the input
Send((bytes + copySize), (len - copySize));
}

Adam Wirth
Thursday, May 20, 2004

floodfill code for a video driver.

Mitch & Murray (from downtown)
Thursday, May 20, 2004

Yesterday. About 20 times.

In compiler writing, one can't go very far without a recursive algorithm. I would guess that there is more than 1000 recursive functions in our code-base.

Employed Russian
Thursday, May 20, 2004

I work with developmen tools and do a lot of lexical analysis and parsing stuff. I probably average a recursive call every couple days (was several a day during initial development).

JT
Thursday, May 20, 2004

grep -r. I use that a lot.

As for actually implementing something recursive, it was probably something to do with walking a tree of parsed HTML or XML.

John C.
Thursday, May 20, 2004

Recently used it in javascript to navigate an HTML table for edit and delete functions (homegrown grid).

yet another anon
Thursday, May 20, 2004

That'd have to be the last time I had full-time work, so about a year ago now. Basically, in order to read data in ANSI X12 271 layout, I built a tree-like map to keep track of where I was as I parsed through the data. Quite a bit of recursion involved in constructing the tree, and again in disposing of it. All in Access VBA.

Slides from a presentation I gave on same at: http://timestream.net/PAUG/

(The talk was titled "OOP: I Did It Again" and was primarily aimed at explaining OOP to self-taught Access consultants who didn't get it.)

Sam Livingston-Gray
Thursday, May 20, 2004

Parse a multi level bill of materials and position the visual maps of processes (one map per level of BOM) so nothing overlapped.

Peter Ibbotson
Thursday, May 20, 2004

Haven't yet, but I need to search a directory tree for tests to run and I'll probably do that recursively.

Snotnose
Thursday, May 20, 2004

Employed Russian, what are you working on?

Pietro
Thursday, May 20, 2004

A few days ago. The reason was simple: traversing a tree-like data structure :) Recursion is a powerful but underrated (and underused) technique.

Davidson
Thursday, May 20, 2004

The first example that springs to mind was a comparison algorithm for matching data rows between a test result and a "test oracle" (the data that the test *should* return). See:

http://cvs.eby-sarna.com/PEAK/src/peak/ddt/processors.py.diff?r1=1.4&r2=1.5

Specifically, the 'compare' method, which uses a recursive approach to partitioning the data sets.

Phillip J. Eby
Thursday, May 20, 2004

Recursion is used all the time in EDA...

Elaboration: need to elaborate instances of submodules before one can completely elaborate the module.

Synthesis: same. Synthesize the submodules first.

Property tracing: one property depends on properties on other instances, which are recursively computed.

The list goes on...

David Jones
Thursday, May 20, 2004

I'm with "anon" on this one. I use recursion quite a bit in my programming, if you really think about it, but in C++ it looks/feels different than procedural recursion because everything is encapsulated in virtual function call loops to child members that are being held in containers.

Mr Fancypants
Thursday, May 20, 2004

Used it 3 seperate times in the last year.

1. our web application has a way for users to upload images in different folders and sub-folders. (and they can create new folders).

2. Our email client needed to support attachments!

3. I needed to walk an XML DOM.

vince
Thursday, May 20, 2004

Couple days ago. All the time really.

For instance, I use recursion lots when processing data in hierarchical formats like XML. As some above indicated, it's a natural and everyday tool for parsing chores.

Wan't some evidence that the guys who designed Java's SAX have probably never written a parser? Compare code using SAX with XML processing code written by anybody who has written a compiler or interpreter. The latter is dramatically clearer, and easier to write and maintain.

Cabby
Thursday, May 20, 2004

It was quick sort algorithm... inside a program written in a language that have not got local variables feature, so I had to create a stack for saving all the data at every level of recursion (simulating local variables in procedure). I bet it's the one and only part of the system using recursion. :)

Ross Sampere
Thursday, May 20, 2004

ASN.1
If you don't know what it is you are lucky.

Doug Withau
Thursday, May 20, 2004

in my homework next week

Thursday, May 20, 2004

Anytime I need to do something generically to each control on a .Net WinForm...

public void DoSomething(Control c)
{
/* Do processing... */
foreach(Control child in c.Controls) DoSomething(child);
}

Also, I've occasionally used recursion to work with arbitrarily deep nested lists within a database, where each row in the table has a Primary Key, a nullable Foreign Key referencing its parent row in the same table, and the item-specific data.

someguy
Thursday, May 20, 2004

Numerous times: an execution tree for a little
scripting language we have in our product, and
a mergesort on smallish linked lists are two I can
think of at the moment.

x
Friday, May 21, 2004

#!/usr/local/bin/python

import os

def printDirectoryContents(dirPath, indent=''):
"""Print a tab-indented list of a directory's entire contents."""
for name in os.listdir(dirPath):
print indent + name
path = os.path.join(dirPath, name)
if os.path.isdir(path):
printDirectoryContents(path, indent + '\t')

printDirectoryContents('/Users/has/Documents/') # TEST

--

The name indenting feature makes the code a little more complicated, but makes it easier for the student to figure out what's going on while studying the output.

A nice feature of this example is you can initially show it without the last two lines so it lists only the top directory's content, then insert them to recursively list all the sub-directories' content as well.

As an extra exercise, the student could enhance the function so it only lists sub-directories to a maximum given depth. (Hint to student: the function would take an extra argument, maxDepth, containing a positive integer that indicates how deep it should go.)

has
Friday, May 21, 2004