Saturday, January 20, 2007

Recursion - the hidden boobytrap laying in wait

So I conjure up a little test case for this project Ive been working on. Nothing terribly complicated:
char c1=0;
char c2=1;
char c3=3;
...
<blah, blah, blah> about 3,000 of them

It turns out that the PUBDEF record loader in this app (written 20+ years ago and virtually unchanged since) used a recursive algorithm to load records where there was an unknown number of repeated subrecords within the main record. It was very elegant. It also fell over dead with stack overrun issues when "n" got large. The 3,000 public's test case can cause "n" to get "large". Modern bloatware apps can cause "n" to get large.

Theoretical elegance, meet harsh reality.
Mr. recursion is going to be hitting the unemployment line after all these years in this instance. You can always substitute iteration where recursion was used and I will be doing so here. I suspect the iterative equivalent will be quite a bit faster as well, since it will be more apt to keep L1 cache's from sloshing full of once-used recursive stack data.

2 comments:

Anonymous said...

I know this isn't one of those cases, but I can't stand it when people use recursion where it is really not appropriate. It's one of those little things where someone may try to prove that they are a better programmer than most of the people around them. Though, I did relish being a CS major who understood recursion when I had to hear the whines of the CIS majors who couldn't even do basic data structures in Java, let alone in C or C++.

Purple Avenger said...

There are other instances of recursion in this program where it does make sense -- the code analyzer's basic block identifier for example.