recursion anxiety
recursion anxiety
- Subject: recursion anxiety
- From: James Maxwell <email@hidden>
- Date: Thu, 25 Mar 2010 09:45:45 -0700
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