CODEWITHSUNDEEP
crecursion
Mahmud Hassan
Mahmud Hassan

Reputation: 29

How to break out of recursion? C Programming

I have a trenary tree every node got id and name how can I return true when root->id=id and break the recursion

BOOLEAN isIdUsed(Trin_Ari *root,int idNumber) {
    if (root==NULL)
        return FALSE;
    if (root->id==idNumber)
        return TRUE;
    isIdUsed(root->left,idNumber);
    isIdUsed(root->middle,idNumber);
    isIdUsed(root->right,idNumber);
    return FALSE;
}

Upvotes: 0

Views: 140

Answers (4)

gkhaos
gkhaos

Reputation: 705

You never backpropagate the results...

BOOLEAN isIdUsed(Trin_Ari *root,int idNumber) {
    if (root==NULL)
        return FALSE;
    if (root->id==idNumber)
        return TRUE;

    if (isIdUsed(root->left,idNumber))
        return TRUE;
    if (isIdUsed(root->middle,idNumber))
        return TRUE;
    if (isIdUsed(root->right,idNumber))
        return TRUE;

    return FALSE;
}

Upvotes: 2

limserhane
limserhane

Reputation: 1050

Your function doesn't take the result of the sub recursions into account. You need to get their returned value to decide if you break the recursion.

BOOLEAN isIdUsed(Trin_Ari *root,int idNumber) {
if (root==NULL)
    return FALSE;

if (root->id==idNumber)
    return TRUE;

if (isIdUsed(root->left,idNumber))
    return TRUE;

if (isIdUsed(root->middle,idNumber))
    return TRUE;

if (isIdUsed(root->right,idNumber))
    return TRUE;

return FALSE;

}

Upvotes: 1

0RR
0RR

Reputation: 1603

how can i return true when root->id=id and break the recursion

You can break the recursion as you mentioned, just check if the root ID is the idNumber and then return false. You can just return the three checks at the end such as:

BOOLEAN isIdUsed(Trin_Ari *root,int idNumber) {
if (root==NULL)
    return FALSE;
if (root->id==idNumber)
    return TRUE;
return isIdUsed(root->left,idNumber) || isIdUsed(root->middle,idNumber) || isIdUsed(root->right,idNumber);
}

Upvotes: 2

Mureinik
Mureinik

Reputation: 311883

You're ignoring the return values from the recursive calls to isIdUsed. Once you encounter a TRUE there, you need to propagate it upwards:

BOOLEAN isIdUsed(Trin_Ari *root,int idNumber) {
    if (root==NULL)
        return FALSE;
    if (root->id==idNumber)
        return TRUE;
    if (isIdUsed(root->left,idNumber))
        return TRUE;
    if (isIdUsed(root->middle,idNumber))
        return TRUE;
    if (isIdUsed(root->right,idNumber))
        return TRUE;
    return FALSE;
}

Upvotes: 2

Related Questions