Recursive function in C returning only once a pointer or NULL

Question

SO i am trying to write a recursive function, in which i only want to have "one" return.

So what I am trying to do is, first I have defined a simple recursive structure:

typedef struct CHAP CHAP;

struct CHAP{

 int ID;
 CHAP** list;
 int nb;

};

Now in my function I want to find and return a pointer to CHAP if it has the same ID as my target. So far I have this:

CHAP* find_chap(CHAP* ch, CHAP* target){

     if (ch->ID == target->ID) return ch;

     for (int i=0; i<ch->nb; i++){
         find_chap(ch->list[i], target);
     }
    //return NULL?
 }

However I am not sure how to return something if the entry is not found? So in that case I would like to return NULL but I don't know where exactly to place it. I am not considering the case if the ID is contained at several entries, then only the first found pointer will be returned.

If I do it in the line where it is commented out, the function and recursion calls will continue even after a entry is found, which is not what i want :/

Should you not check what the recursive call to find_chap return? — Some programmer dude
– Some programmer dude, Commented Jan 19, 2017 at 10:39
Returning NULL if no entry iks found seems appropriate here. BTW you don't need recursion here. — Jabberwocky
– Jabberwocky, Commented Jan 19, 2017 at 10:41
Well I need a recursion because the entries of the ->list can also then have again an allocated ->list and so on... — malajedala
– malajedala, Commented Jan 19, 2017 at 10:53

WhozCraig · Accepted Answer · 2017-01-19 10:57:07Z

1

You need to:

Record whether the current parameter ch matches your target
Loop over the ch child nodes until either you have a match to return (which you may already) or exhaust the list.
Return the result of the above.

In short, something like this:

CHAP* find_chap(CHAP* ch, CHAP* target)
{
    CHAP *res = (ch->ID == target->ID) ? ch : NULL;

    for (int i=0; !res && i<ch->nb; ++i)
        res = find_chap(ch->list[i], target);

    return res;
}

That should fulfill your requirement of having a single return point in the function, while still recursing children.

answered Jan 19, 2017 at 10:57

WhozCraig

66.5k11 gold badges82 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

malajedala Over a year ago

Can you tell me what the !res in the loop is standing for. I have seen this notation before but i could not find anywhere an explanation. I am confused because res is a pointer and not a bool or integer value

WhozCraig Over a year ago

@malajedala that's the test for whether res is still NULL or not. It is equivalent to (res == NULL). The loop will break as soon as (a) res is non-NULL, or (b) i has met ch->nb. Note that if res was already set to non-NULL on the first line because ch->ID == target->ID, then the loop effectively becomes a noop and no iterations take place; !res becomes false and therefore the for-condition is no longer meetable.

malajedala Over a year ago

Oh I see. I just tried your example and it is exactly what I was trying to do. Thank you so much for your help and your explanations!

Serge Ballesta · Accepted Answer · 2017-01-19 10:55:59Z

1

You forgot to return a value from the recursive call:

CHAP* find_chap(CHAP* ch, CHAP* target){

     if (ch->ID == target->ID) return ch;

     for (int i=0; i<ch->nb; i++){
         CHAP * c = find_chap(ch->list[i], target);
         if (c != NULL) return c;         // return not null value if one was found
     }
    return NULL;   // not found here...
 }

answered Jan 19, 2017 at 10:55

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

Collectives™ on Stack Overflow

Recursive function in C returning only once a pointer or NULL

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related