- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
Years ago I worked on a product where most of the code was written in fortran. While fortran does support recursion, it had a compiler option (-static or something like that) which would make all functions static and prevent you from writing recursive code. Someone had used that option for reasons that no one could remember any more, but no one would change it for fear of breaking something. At least it was a compile time error.
Admin
Fixed it for ya .. free of charge.
Admin
Yes, from a pure computer-science perspective, any language that supports functions supports recursion, but real-world implementations may vary from this ideal.
Admin
OBviously, this would be better handled with a loop:
Sub Main()
Console.WriteLine("Public Function GetNestingLevel(objNode As Node)")
Console.WriteLine(" If Not objNode.Parent Is Nothing Then")
Console.WriteLine(" GetNestingLevel = 0")
For i As Integer = 1 To 59
Console.Write(" ElseIf ObjNode.parent")
For j As Integer = 1 To i
Console.Write(".parent")
Next
Console.Write(" is nothing then " & vbNewLine)
If i = 4 Then
Console.WriteLine(" If objNode.NodeId = 3382 Then")
Console.WriteLine(" GetNestingLevel = 3")
Console.WriteLine(" Else")
Console.WriteLine(" GetNestingLevel = 4")
Console.WriteLine(" End If")
Else
Console.WriteLine(" getNestingLevel = " & i)
End If
Next
Console.WriteLine("Else")
Console.WriteLine(" GetNestingLevel = 60")
Console.WriteLine("End If")
End Sub
Admin
Most languages don't implement tail-recursion optimizations though, which makes them extremely unfit for higly recursive stuff because you blow the stack every time.
Some languages work only by recursion, and are amazingly good at it.
Limitation is usually not artificially limited, it's just the language/computer running out of stack space and displaying an error instead of completely blowing your stack.
Admin
In my diploma program, they deliberately omitted it. Given the time constraints, I might well have done the same. I have used recursion a couple of times, but have not found it that useful for what I do. Obviously, YMMV.
At least, they did not teach with that stupid factorial example.
Sincerely,
Gene Wirchenko
Admin
Actually, that solution looks like it will fix the null pointer exception that will be thrown when a root node hits the first else if too.
Admin
Sadly, Greg will very soon have to live with these programmers looking down at him for his "lack of technical ability".
captcha: clueless
Admin
Scene 1, Friday, 1:30 PM at Initech
Sr. Dev #1: Hey you, what's your name?
FNG: Freddie Noogeye.
Sr. Dev #1: Yeah, I knew that. Listen, ya know that GetNestingLevel method you wrote? Well, the customer needs to add 500 more levels of nodes.
FNG: But that code took me all week to figure out. It's Friday!
Sr. Dev #1: Yeah, I know that. But the customer needs it by the end of the day. Get right on that will ya?
FNG: Um... okay. <tap, tap tappity,tap>
Scene 2, Friday, 5:00 PM at Initech
FNG: <tap, tap tappity,tap>
Sr. Dev #2: What's the FNG doing?
Sr. Dev #1: Heh... he's tap tap tappity tapping away, ain't he?
FNG: <tap, tap tappity,tap>!!!
Sr. Dev #2: You got him that GetNestingLevel update? I thought you were going to show him how to do it right.
Sr. Dev #1: Yeah, but this is much more fun to watch.
Sr. Dev #2: You're a bastard, dude.
Sr. Dev #1: Yeah, wanna stop for a beer on the way home?
Sr. Dev #2: Okay. You buying?
FNG: <tap, tap tappity,tap>!!!!!
Admin
Nope, still wrong. I've coded in a language that had no recursion abilities.
Think of a language with no stack at all, so it can't stack return addresses. No local variables, either - everything is global. And yet, not only did it have function calls, it had multi-tasking.
Oh, and this was an assembler, one that had a single bit accumulator ... no, you've not programmed until you've done PLC work.
Admin
It used be the case in the 90s. Anyone who knew how to turn a computer on could walk into any company and get hired on the spot. Now, a CS degree is nearly worthless without relevant work exp in the field.
Admin
Will this method get past the first If check?
Whether objNode is 1 level down, or 20 levels down, the first If check is that objNode.Parent is NOT Nothing, which will be true regardless of level.
All other Ifs are checks for Nothing. But they are ElseIfs and so will not get run once the top If equates to True.
Admin
You mean that nesting level might be something like 'FILE-NOT-FOUND'??? Brillant!
Captcha = genius - love it
Admin
The verb is actually "to recur," not "to recurse." As my CS prof always said, "To recur is to reexecute the same logic; to recurse is to curse again."
//CAPTCHA = craptastic
Admin
The problem with that is that the NodeId = 3382 special case needs to be done at the end, so we'd need a separate recursive function to be called by this one if we want to use recursion. Now, you may want to argue that you were discussing the general case and not this specific function, but even without the special case, we'd need a separate function, since we'd have to pass in the current level.
So, to sum up, you are advocating a method, which
IOW, yes, you are the one who's "WTF-enabled."
Admin
Anyone hear of tail recursion?
Admin
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>The real WTF here is that:</FONT>
<FONT face=Arial>RECURSION ERROR!!!</FONT>
<FONT face=Arial></FONT>
Admin
Admin
If the first test fails, then objNode.Parent is Nothing, and there isn't going to be any objNode.Parent.Parent or objNode.Parent.Parent.Parent and on etc. The nesting level will either be 0 (the first test is true) or else it will default to the last one and become 60.
Xocomil nailed it.
Admin
Truthfully, if you had discovered this code in soething you had to maintain, might you not be cursing again?
Admin
Not saying that dictionary.com is the definitive english language source, but they define it as a computer term meaning " To perform recursion" .... of course, now we're just being picky ;-P
Admin
On taking a longer look... I wonder how VB would deal with the parent of a null object? Would it throw an error, or return the null object's parent as null also? In the latter case the possibilities would be either 0 or 1..
Admin
<FONT face=Georgia color=#800080 size=4>I think this is pretty good code coming from the janitor and sales team!</FONT>
<FONT face=Georgia color=#800080 size=4>What? You mean this small software company actually has real developers on the payroll? Where are they? And when does Greg get to manage them, too? And how will he prioritize between these developers, the sales team, and the janitor?</FONT>
<FONT face=Georgia color=#800080 size=4>Now I'm confused. <FONT color=#ff0000>;-P</FONT></FONT>
<FONT face="Courier New" size=2><FONT color=#0000ff>If</FONT> objNode <FONT color=#0000ff>Is Nothing Then</FONT>
GetNestingLevel = 0 <FONT color=#008000>' "I'm my own Grandpa!!"
</FONT><FONT style="BACKGROUND-COLOR: #0000ff"><FONT style="BACKGROUND-COLOR: #ffffff" color=#0000ff>End If</FONT>
</FONT></FONT>
Admin
Anyone read the comments before posting?
Admin
Exactly.
Admin
Please tell us then what method did they use for tree traversal??? (Yes, I know it can be done iteratively - it just shouldn't).
Captcha: paula :)
Admin
What a great manager! Your "subordinates" submit what they think is their best work and you throw it out here to be ridiculed. You must be a great person to work for/with.
Admin
10 PRINT "CAN ANCIENT BASIC RECURSE"
15 REM I THINK YOU COULD ARGUE THIS IS RECURSION WITH NO STACK
20 GOTO 20
Admin
If we're working with XML (and the API supports XPath calls), we can just say:
NestingLevel = objNode.selectNodes("ancestor::*").length + 1
Admin
And by that definition, iteration and recursion are only theoretically equivalent, if we exclude the theoretical case of an infinite (well, to the boundary conditions) nesting where recursion should overflow the stack at some arbitrary point, and iteration might throw an increment overflow exception if you're very lucky.
As for this particular WTF, well, I guess it's just a good thing nobody here has worked with a language which allows "circular parentage" (in the manner of circular linked lists). Of course, the example application excludes such things so at least it doesn't have to worry about the consequences.
Admin
Dude, that was absolutely awful, and that was what he thought was the best of what his subordinates submitted. Frankly, it's such a WTF that I'm tempted to buy flowers for his next of kin and send my condolences in advance.
Admin
Relying upon the compiler to do the tail recursion optimization is a bad idea. If optimizations get turned off for any reason, nasty things will start happening.
"Frank, the program works fine in release mode, but whenever I try to debug it, BOOM!"
Admin
Consider getting yourself a compiler that does tail-call elimination. There are lots to choose from. Including gcc, btw.
And there is nothing simple about iteration.
Admin
100 REM RECURSION EXAMPLE
110 LET L=10
120 GOSUB 200
130 PRINT "MOST INEFFICIENT WAY TO SET L TO 0 COMPLETED"
140 END
200 LET L=L-1
210 IF L>0 THEN GOSUB 200
220 RETURN
Admin
int GetNestingLevel(Node theNode) {
// StupidEnterpriseyLookup should probably be class scoped, static, readonly, but...
HashMap<int,int> <int,int> StupidEnterpriseyLookup = LoadLookupList();
if (StupidEnterpriseyLookup.Keys.Contains(theNode.NodeId))
return StupidEnterpriseyLookup[theNode.NodeId];
Node node = theNode;
int depth = 0;
while (node.Parent != null)
{
depth++;
node=node.Parent;
}
return depth;
}
// okay, so a sparse array would be describe this better. oh well.
private HashMap <int,int> <int,int> LoadLookupList()
{
HashMap <int,int> result = new HashMap<int,int>();
result[3382] = 3;
// add other 'business logic specials' here.
return result;
}</int,int></int,int>
Admin
... they will start teaching recursion when they start teaching recursion.
Admin
This is from Wikipedia.
"Newcomers to recursion are often bewildered by its apparent circularity, until they learn to appreciate that a termination condition is key."
So that isn't recursive, bcause there is no termination.
Captcha = null
Admin
I do not see that that the iterative approach is so bad. If you were tight for space and did not need local variables, allocating a pointer might have less overhead than a subroutine call. (Yes, the recursive code is easier to read.)
You can keep her.Sincerely,
Gene Wirchenko
Admin
I find it hard to believe Alex didn't name this thread "Meet the Parents"
CAPTCHA can't spell: mustache
Admin
Aside from the issue of expense, why not to the next of kin of the subordinates?
Sincerely,
Gene Wirchenko
Admin
Admin
To allow for negative values:
200 L=L-SGN(L)
210 IF L<>0 THEN GOSUB 200
The handling of floats is left as an exercise to the student.
Sincerely,
Gene Wirchenko
Admin
Quote from Suffer:
Okay, Java version, with strange undocumented case handled...
public int getNestingLevel( Node objNode) {
int level = 0;
Node currentNode = objNode;
while ( currentNode.parent() != null ) {
level++;
currentNode= currentNode.parent();
}
if (level==4 && objNode.id()==3382) {
level = 3;
}
return level;
}
Brillant!
Unquote
******************
I'm not sure that the logic is quite right here.
This is how I'd do it:
int ReturnNestingLevel ( )
{
NestingLevel = -1;
While (ObjNode.Parent != NULL)
{
if(ObjNode.NodeID == 3382 & NestingLevel==2)
{
NestingLevel = 3;
Return NestingLevel;
}
else if(ObjNode.NodeID != 3382 & NestingLevel==2)
{
Nesting Level == 4;
ObjNode.Parent = ObjNode.Parent.Parent;
}
//all other cases where NestingLevel != 2
else
{
Nesting Level ++;
ObjNode.Parent = ObjNode.Parent.Parent;
}
}
return NestingLevel;
}
-- JT
Admin
Sorry,
Meant to initialize NestingLevel as 0, not -1.
- JT
Admin
Most inefficient? What about this:
200 LET L=L/2
Admin
Or
200 L=RND(0)
or 1 or whatever the parm should be. This varies between dialects.
Sincerely,
Gene Wirchenko
Admin
More stupid recursion tricks.
Friend and I went to the University of Waterloo, that's in Canada... the big thing tucked away up there. Anyway, we were in an introduction to CS course (cs130 is what it was called back in the day). During our written midterm, there was a question asking how to get this robot object (which exposed certain methods to make it move and do stuff) to do something in a pattern.
Anyway, most people did it iteratively. Friend of mine used recursion, and it would have worked fine too. But the TA's gave him a 0 on it. On appeal to the prof, still, 0. Why? "You aren't supposed to know about recursion yet"
Though he did note in the next term's class, the question was changed to add this at the beginning, "Without using recursion, do the following..."
captcha=craptastic
Admin
And oops again, the test should have been against NestingLevel ==3, not 2. But I think the logic is correct and it handles the weird case OK.
- JT
Admin
Oooooh, forbidden knowledge!
I would have then taken it up with the department chair. I did that in one course. Said department head said to give me the mark.
I had one instructor that I put a certain amount of fear into. When I challenged him on deducting marks because I did not validate a name by checking that it was not numeric, he challenged me to come up with a case of a numeric name. I came up with two.
Sincerely,
Gene Wirchenko
Admin