Two recursive functions returning in unexpected order

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Greetings, Monks.

Boy, do i have a doozy for you!!!

I have a program, which contains 2 functions. (well - more than 2, but only 2 are relevant). Both of them are recursive, and the second gets called from the first. The first one does some processing on database tables, and then calls itself to process that tables children. It then calls the second to process it's parents... Enter the explanatory code snippet:


#!perl



<snip>


    buildSQL($starttable, $startwhere)

<snip>
.
.
.
.
.
.


sub buildSQL
{
    my $table=shift;
    my $where=shift;

    $level++;
    $ischild{$table}=1;

<snip>

    foreach my $child (keys($tables{$table}))
    {

<snip>

        print STDERR "About to gen SQL for $child, child of $table\n" 
+if $table =~ m/Test2/;

<snip>

        buildSQL($child,$wh);
    }
    buildParentSQL($table);
    $level--;
}


sub buildParentSQL ()
{
    my $table=shift;

<snip>

    foreach my $parent (@{$parents{$table}})
    {
        next if defined($ischild{$parent};
        print STDERR "Generating parent SQL for $parent, parent of $ta
+ble\n" if $parent =~ m/Test2/;

<snip>

        buildParentSQL($parent);
        $level--;
    }
}
[download]

Which looks OK to me. The plan is, it enters buildSQL, sets some data in a hash (ugly code which i've removed for brevity and sanity), and then calls itself for each child entity of the one it's just completed. Once it's done all the work on itself, and all of it's children, it's time to work on it's parents - hence the call to buildParentSQL.

What i expected to happen: A large stack of buildSQL would build up, setting $ischild for each one as it goes. Only once the last buildSQL has completed, should the buildParentSQL's start getting called.

Because of the next therein, any table which is a child gets ignored, but any which isn't get appropriately dealt with.

Now, the weird part. Enter sample output:

Generating parent SQL for Test1, parent of Test2 About to gen SQL for Test3, child of Test2 About to gen SQL for Test4, child of Test2

The first line of output comes from the second function (buildParentSQL)!! How can this be? Surely, SURELY, all the children from the first function should have done their output, before the second function even got called!

Now enter even more weirdness: I figured 'OK, It creates a pipeline of sorts, into which it's inserting the prints and things, and only flushes that when the function completes'. So I moved the buildParentSQL call to be the first thing in the buildSQL function (except for shifts etc), and ran it again. Identical output.

How can this be?

Hopefully, some-one knows whats going on here, because i can't figure it out... It must be something do with the recursiveness of it all, but to my mind it looks OK. Haven't tried in any other languages yet, though that may be a next step....

Ideas, suggestions, and the pointing out of stupid mistakes all welcome. (especially the last).

Thanks

Comment on Two recursive functions returning in unexpected order Select or Download Code

Replies are listed 'Best First'.
Re: Two recursive functions returning in unexpected order by ikegami (Patriarch) on May 11, 2005 at 04:47 UTC
buildSQL:1 calls buildSQL:2. buildSQL:2 calls buildParentSQL. buildSQL:2 returns. buildSQL:1 calls buildParentSQL. ("function:#" reflects recursion.) So buildParentSQL can be called before the print in (a different) buildSQL. On an unrelated note, `sub buildParentSQL ()` should be `sub buildParentSQL` Don't use prototypes unless you must, especially incorrect prototypes.	[reply] [d/l] [select]
Re: Two recursive functions returning in unexpected order by spurperl (Priest) on May 11, 2005 at 04:45 UTC
First look at the obvious. buildParentSQL can print stuff before buildSQL if the loop in buildSQL doesn't execute. Are you sure that `(keys($tables{$table}))` is what you want in there ? Hard to tell w/o knowing what $tables is, but it looks a little fishy. Such problems in general are easy to resolve with extra printouts. In the beginning of every function insert a printout of "foo called" (possibly with its arguments) and in the end a printout of "foo returns" (possibly with what it returns). Then, run on a small example - this will sure clear things up for you.	[reply]
Re^2: Two recursive functions returning in unexpected order by Argel (Prior) on May 11, 2005 at 18:43 UTC
Such problems in general are easy to resolve with extra printouts. I usually like to use a subroutine for this and then call it at the beginning of every other subroutine in the script. `sub whoami { print "DEBUG: ".(caller(1))[3]."\n" if $DEBUG > 0; } sub dostuff { whoami(); <snip> }` [download] -- Argel	[reply] [d/l]
Re: Two recursive functions returning in unexpected order by K_M_McMahon (Hermit) on May 11, 2005 at 04:53 UTC
UPDATE: Wow, I start my response when there are no others, walk away for a second and 2 people submit before me....and unbelievably, noone else says to turn on warnings or to use strict! ;-) First off, try turning warnings on `#!/usr/bin/perl -w` and also always `use strict;` That should be on anyway... but if you are having problems it can help find the location. your line `foreach my $child (keys($tables{$table}))` shouldn't work. you can't call `keys` on a hash if you are actually calling a value out of the hash. try `foreach my $child (keys(%tables))` you also have references to other variables `foreach my $parent (@{$parents{$table}})` that we can't see where you are generating these variables.... Try posting more of the code. If it is long, use readmore tags. -Kevin `my $a='62696c6c77667269656e6440676d61696c2e636f6d'; while ($a=~m/(^.{2})/s) {print unpack('A',pack('H*',"$1"));$a=~s/^.{2}//s;}` [download]	[reply] [d/l] [select]
Re: Two recursive functions returning in unexpected order by Zaxo (Archbishop) on May 11, 2005 at 04:56 UTC
Do you get something that fits your expectations better if you leave the conditionals off the diagnostic prints? The loop in `buildSQL()` looks funny. The list `keys($tables{$table})` is going to be empty. I suspect you mean: `foreach my $child ( keys %{$tables{$table}})` I could make better sense of this if I could see the boring parts where you set up the data. After Compline, Zaxo	[reply] [d/l] [select]
Re: Two recursive functions returning in unexpected order by Anonymous Monk on May 12, 2005 at 05:12 UTC
Cool - I appear to have it working now. I pulled it out into two recursives, so the main body is now: `buildSQL($starttable, $startwhere); buildParentSQL($starttable);` [download] I eventually found a reasonably fundamental bug - so it's possible i could have got it going the original way... But this way will be easier to maintain. And there's no way I'm touching this code anymore than i have to now!!! Thanks for your input guys - It definately helped me find the issue. It's great to see a community of such helpful people!	[reply] [d/l]
Re: Two recursive functions returning in unexpected order by thcsoft (Monk) on May 11, 2005 at 08:58 UTC
hmm.. admittedly this post isn't very much helpful here. but i'm asking myself, why the compiler doesn't complain of a "deep recursion". language is a virus from outer space.	[reply]
Re^2: Two recursive functions returning in unexpected order by Anonymous Monk on May 11, 2005 at 21:35 UTC
wow - great responses! Most abundant question first - the keys($table{$table}): One of the later posters was right - it's meant to be %{$tables{$table}}. Though in the actual code it's (%$table) - I changed it to make it slightly more readable (when i wrote the first version of the code, i was still getting the hang of using variables as variable names {is there a name for this practise?}, and haven't been brave enough to change all the legacy code - if i were to do it again, this is how it would look). > First look at the obvious. buildParentSQL can print stuff before buildSQL if the loop in buildSQL doesn't execute I think you've started me on the right track here - There could be no children left under the first child at level 3, so it drops back to level 2, runs parentSQL, and then moves into another child at level 3! While this arguably still shouldn't account for what I'm seeing, combine it with an unfortunate sequence of foreign key relationships, and it's quite possible for a table to called as a parent, before it gets called as a child. The solution here will be to pull parentSQL out of buildSQL, and borrow of lot of the code from it for the looping. Slightly less elegant, but this script has long since passed the asethetic phase of its life! > On an unrelated note, > `sub buildParentSQL ()` > should be > `sub buildParentSQL` > Don't use prototypes unless you must, especially incorrect prototypes. Noted - cheers! Not sure why i do it this way - probably a habit picked up from shell scripting > If it is long, use readmore tags. ??? Will try running with strict, warnings, non-embedded recursion and all the other suggestions here today, and update you with my progress. It's a large and ugly script to setup the data - I barely understand it myself these days, so i don't want to pain you with it - the guts of it is though: - read in a human readable dump of the database schema (dbschema -d <db> -t all, for the informix ppl out there) - Parse it, to get: a hash of tables and their primary keys ($pkeys{<table>}=<primary-key>), a hash of tables, and their columns (push(@{$cols{$table}},<col>), a hash of children and foreign keys ($<table>{$child}=<foreign-key>). (this one is the hash you are seeing in the loop. - Call buildSQL for the start table. - Enter recursive hell. I'll post again in a few hours with an update.	[reply] [d/l] [select]