Recursive code for a tree function?

Question

I have a function that returns the first node of a tree,

node* primeiro(tree r){
    while(r->left != NULL){
        r = r->left;
    }
    return r;
}

BTW, the percuss is made in order. So the function returns the leftmost leaf of the tree and the function presumes that the tree is not empty. How can I implement this in a recursive way?

 node* primeiro (tree r) {
    while (r->left != NULL) {
     r = primeiro (r->left); 
    }
    return r;
}

This is not working.

Define "_not working_". Is it crashing, not compiling, giving you an unexpected result, nothing at all? — litelite, Aug 28 '17 at 19:28

score 2 · Answer 1 · answered Aug 28 '17 at 19:30

2

The problem is in using while. You need simple recursion termination condition.

node* primeiro (tree r) {
    if (r->left != NULL) {
        r = primeiro (r->left); 
    }
    return r;
}

answered Aug 28 '17 at 19:30

kocica

6,412
2
14
35

score 0 · Answer 2 · answered Aug 28 '17 at 19:40

0

Instead of using condition r->left != NULL for while loop, check it for true or false. (that will be base condition for the termination of recursion).

answered Aug 28 '17 at 19:40

Vikram Kumar

94
6

2

What does this add to the prior answer? – Prune Aug 28 '17 at 19:54
The question was unanswered, when i saw it. – Vikram Kumar Aug 28 '17 at 20:08

autistic · Answer 3 · 2017-08-28T20:12:11.810

When we speak of "recursive functions", we usually mean "functions that use recursion to loop"...

Both of your functions are using while to loop. You should focus on transforming that while loop into a recursive function call.

Consider this loop:

int fubar(int x) {
    while (x > 0) {
        x--;
    }
    return x;
}

It transforms into this:

int fubar(int x) {
    if (x > 0) {
        return fubar(x - 1);
    }
    return x;
}

Notice how similar the two are. The differences are:

You're changing x not directly but by passing a different value of x in
Your loop test is in an if statement, not while...
Again, you're not looping using while; instead you should be calling fubar again, passing in a new value and returning its result.

Important note: There could be significant benefits to ensuring every recursive function call is followed immediately by a return (without any intermediate calculations required).

score 0 · Answer 4 · answered Aug 28 '17 at 20:34

When iteration is being replaced with recursion, it may be easier to derive the right code by beginning with the infinite recursive loop:

node* primeiro(tree r){
    /* What goes in the recursive loop body? */
    return primeiro(r);
}

You can now ask under what would the next value of the iteration, and when does the loop stop. The next value is pretty straight forward.

node* primeiro(tree r){
    /* When does the recursive loop stop? */
    r = r->left;
    return primeiro(r);
}

From the while loop logic, the loop stops when r->left is NULL. At that point, you would return r.

node* primeiro(tree r){
    if (r->left == NULL) return r;
    r = r->left;
    return primeiro(r);
}

Recursive code for a tree function?

4 Answers4