Re: recursion anxiety
Re: recursion anxiety
- Subject: Re: recursion anxiety
- From: James Maxwell <email@hidden>
- Date: Thu, 25 Mar 2010 10:05:37 -0700
LOL!!!
Yipes, how embarrassed am I????
So clever, yet so stupid...
thanks a million.
J.
On 2010-03-25, at 9:58 AM, Howard Siegel wrote:
> You never seem to be capturing the result of the recursive calls for return to the caller.
>
> You final if block should look like this:
>
> if(([endNode depth] < ([self contextDepth] - 1)) && ([mutableSeq count] > 1) && (found == YES))
> {
> [mutableSeq removeObjectAtIndex:0];
> endNode = [self getTrieNodeFromContextSequence:mutableSeq withNode:endNode];
> }
>
> - h
>
> On Thu, Mar 25, 2010 at 09:45, James Maxwell <email@hidden> wrote:
> Hi Folks,
>
> I've had problems with recursive functions before, but this one's making me crazy.
> I have a trie (tree) data structure and I'm trying to find a sequence of ints in the trie.
>
> - (HSMM_TrieNode*) getTrieNodeFromContextSequence:(NSMutableArray *)aSequence withNode:(HSMM_TrieNode*) aNode
> {
> int coincidence;
> BOOL found = NO;
> HSMM_TrieNode* endNode = nil;
> NSMutableArray* mutableSeq = [[NSMutableArray alloc] initWithArray:aSequence copyItems:YES];
> for(HSMM_TrieNode* child in [aNode children])
> {
> coincidence = [[mutableSeq objectAtIndex:0] intValue];
> if([child coincidenceID] == coincidence)
> {
> endNode = child;
> found = YES;
> break;
> }
> }
> if(([endNode depth] < ([self contextDepth] - 1)) && ([mutableSeq count] > 1) && (found == YES))
> {
> [mutableSeq removeObjectAtIndex:0];
> [self getTrieNodeFromContextSequence:mutableSeq withNode:endNode];
> }
> [mutableSeq release];
> return endNode;
> }
>
> The caller sends the sequence of ints (NSNumbers) and the root node of the trie to search. If I NSLog the guts of this method, I can see that it is, in fact, recursing down the trie, and correctly following the branch with the matching ints (coincidenceID numbers), and reaching the point I need to reach. The problem is that it's not returning the last node in the trie (i.e., the last match), but rather is returning the first match. And I have no idea why...
> Those last few tests before recursing are just checking that 1) I haven't gone too deep in the trie (I actually want the last node *before* the leaf -- "contextDepth" is the max depth of the trie), 2) that I haven't run out of ints in the sequence, and 3) that I actually found branch to continue searching down. If trie doesn't have a match for the start of the sequence, the nil return is handled by the caller.
>
> Can anyone see why the caller is getting the first match, rather than the last?
> Immense thanks to anyone who can see what's up.
>
> J.
>
>
> James B Maxwell
> Composer/Doctoral Student
> School for the Contemporary Arts (SCA)
> School for Interactive Arts + Technology (SIAT)
> Simon Fraser University
> email@hidden
> email@hidden
>
> _______________________________________________
>
> Cocoa-dev mailing list (email@hidden)
>
> Please do not post admin requests or moderator comments to the list.
> Contact the moderators at cocoa-dev-admins(at)lists.apple.com
>
> Help/Unsubscribe/Update your Subscription:
>
> This email sent to email@hidden
>
James B Maxwell
Composer/Doctoral Student
School for the Contemporary Arts (SCA)
School for Interactive Arts + Technology (SIAT)
Simon Fraser University
email@hidden
email@hidden
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden