Re: recursion anxiety
Re: recursion anxiety
- Subject: Re: recursion anxiety
- From: Howard Siegel <email@hidden>
- Date: Thu, 25 Mar 2010 09:58:13 -0700
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
>
_______________________________________________
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