Help with function recursion

[gemelli]

I know, I know ... to some of you, "recursion" is most likely a dirty word That being said, I'd like some help with it just the same.

What I am trying to do is build an ASH function whose purpose is to examine an integer map, and return a string that specifies the keys in that map whose summed values come closest to a specified target value. The attached file is an abbreviated version of my function, stripped down to its base logic to illustrate the problems I'm having.

The purpose of this code is to try and test all possible combinations of the values in the statchange[] map, and to see which one of them comes closest to the given "howmuch" parameter. As it goes through, the function updates global variables `closest` (which stores the current "champion" value closest to howmuch), `closelist` (which stores the current list of map keys associated with the champion), and `closecount` (which stores the # of items in the champion list).

The basic flow is:

* Check the current summed value of the mapped integers defined by the keys in testlist
* If the summed value is closer to `howmuch` than the current closest value, crown a new champion
* If the summed value is equally close to `howmuch` than the current closest value, AND has fewer items in its list, crown a new champion
* Iterate through all of the keys in statchange[] to see if we can add a new one to testlist ... if so, recursively call the function with the appropriate appended term to testlist.

Based on how this would work in (for example) PHP, I would expect the function to recurse itself with the following values of testlist:

(null)
::1
::1::2
::1::2::3
::1::3
::2
::2::3
::3

However, the actual output is as follows:

Testlist:
combined=0 from
Checking key 0
Checking key 1
Testlist: ::1
combined=2 from ::1
Checking key 0
Checking key 1
Checking key 2
Testlist: ::1::2
combined=-1 from ::1::2
Checking key 0
Checking key 1
Checking key 2
Checking key 3
Testlist: ::1::2::3
combined=-6 from ::1::2::3
Checking key 0
Checking key 1
Checking key 2
Checking key 3
Completed findSum for ::1::2::3
Checking key 3
Checking key 2
Checking key 3
Looking for a sum of: -8... we can do -6
Closest list: ::1::2::3

There are a few things that seem to be going wrong here:

(1) The `foreach key in statchange {` code is running through once for a key of 0, even though no such key is defined in the statchange[] map
(2) Although findSum() is recursively called three times, the `Completed findSum` message only appears once

So there are clearly some aspects of ASH recursion that I don't understand Can someone help point me in the right direction? (And if there's a simpler way to handle the "find a sum" problem described above, please let me know!)

 

[Veracity]

I only have time to comment on one of your questions for now. Sorry!

[quote author=gemelli link=topic=867.msg4224#msg4224 date=1176938188]
(1) The `foreach key in statchange {` code is running through once for a key of 0, even though no such key is defined in the statchange[] map[/quote]

You are adding it to the map via:

		combined=combined+statchange[checkNum];

with checkNum = 0;

To see why that happens, look at this:

void split( string testlist )
{
    string [int] thisTest = split_string(testlist,"::");
    int testCount=count(thisTest);

    print(" string = " + testlist + " count = " + testCount );

    foreach key in thisTest
        print( "key = " + key + " string = " + thisTest[ key ] );
}

split( "" );
split( "::1" );
split( "::1::2" );

which results in this output:

> split.ash

string = count = 1
key = 0 string =
string = ::1 count = 2
key = 0 string =
key = 1 string = 1
string = ::1::2 count = 3
key = 0 string =
key = 1 string = 1
key = 2 string = 2

In other words, split_string is returning an empty string for whatever is in front of the first "::", which converts to 0.

 

[gemelli]

[quote author=Veracity link=topic=867.msg4226#msg4226 date=1176951885]
I only have time to comment on one of your questions for now. Sorry![/quote]
Not a problem! I appreciate any help you can offer.

It wasn't obvious to me that you could create a new key in a map simply by evaluating whether there is anything in that key; thank you for clearing that up. That should be simple to code around.

I'll keep playing around with the recursion stuff in the meantime to see if anything obvious jumps out at me. If I had to hazard a guess, it would be that the values of function-specific variables aren't returning to their pre-recursion values after the recursed function completes. If that makes any sense.

 

[Veracity]

[quote author=gemelli link=topic=867.msg4233#msg4233 date=1177001209]
It wasn't obvious to me that you could create a new key in a map simply by evaluating whether there is anything in that key; thank you for clearing that up.  That should be simple to code around[/quote]

You aren't "evaluating whether there is anything in the key". You are "asking for the current value associated with the key" - and if you haven't set it, it sets it to the datatype specific default value and returns that.

If you want to see if a key is set, use "<map slice> contains <key expression>"

I'll keep playing around with the recursion stuff in the meantime to see if anything obvious jumps out at me.  If I had to hazard a guess, it would be that the values of function-specific variables aren't returning to their pre-recursion values after the recursed function completes.  If that makes any sense.

Yes, that was my guess too: it looks to me like, perhaps, all local variables are effectively "static".

I started to write a small recursive function to test that, but my first version did not adequately test it and when I modified it, I couldn't get KoLmafia to recognize that I'd changed the function; it was as if it had saved away the original version of the function and wanted to use that instead of the newer version. I have no clue about why that should be, but I ran out of time to work on it and punted.

Between now and May 8, when I go away to a conference, I have to finish 3 big school projects. Until I return from the conference, recreational Java programming is not on my plate...

Edit: from clean build of KoLmafia, I tried the following script:

void recurse( int input )
{
    int local;
    print( "input = " + input + " local = " + local );
    local = input + 1;
    if ( local < 3 )
        recurse( local );
    print( "After call: local = " + local );
    local = -1;
}

recurse( 0 );

...and got the following results:

> tr.ash
input = 0 local = 0
input = 1 local = 0
input = 2 local = 0
After call: local = 3

...which sure looks like returning from the recursed function frame actually returns from the outermost frame of that function. That sure looks like a bug. Local variables may or may not always be static - and if they are, I'd call that a bug, too - but the first bug would trump that one...

 

[gemelli]

[quote author=Veracity link=topic=867.msg4234#msg4234 date=1177014397]...which sure looks like returning from the recursed function frame actually returns from the outermost frame of that function. That sure looks like a bug. Local variables may or may not always be static - and if they are, I'd call that a bug, too - but the first bug would trump that one...[/quote]

OK, whew.  I was starting to worry that it was just me  (And apologies for my lack of good programming terminology ... I never got any formal training in this stuff.)

I'm going to try to come up with a non-recursive way to solve this problem in the meantime -- ow, ow, ow -- but many thanks for taking the time to clarify the situation!

EDIT: I came up with an interim workaround. The attached script solves the problem, essentially creating a mini-recursion architecture of its own. It's neither perfect nor elegant, but it does get the job done.

 

[holatuwol]

Handling of recursion believed to be fixed for 11.0.

 

[gemelli]

/me grovels in deep, heartfelt thanks