Returning a value in recursion

Question

I'm new to stackoverflow so feel free to change or edit my question as necessary.

I have the following code that I'm trying to fix, it is essentially just a inorder tree traversal:

void *inorder_traversal(void *heapstart, uint32_t size, void *address) {
    struct node *head = (struct node* )heapstart;
    if (head->left_child == NULL) {
        if (condition1) {
            if (condition2) {
                address = head->address;
            }
        }
    } else {
        inorder_traversal(head->left_child, size, address);
        inorder_traversal(head->right_child, size, address);
    }
    return address;
}

I'm currently trying to return a void * that is stored inside one of the nodes I'm going through. This node must satisfy the condition1 (size < pow(2, head->initial_size) && size > pow(2, (head->initial_size) - 1)) and condition2 head->current_state == free. I have removed these from the code for ease of reading.

My issue arises when I am trying to extract the address and return it. I have that address = head->address. However because head is changing whenever recursion occurs, head->address always points to the last nodes head->address and not head->address that fulfils my condition.

Essentially i'm asking if there is a way to break the traversal whenever the condition is satisfied and return the address that I have stored.

Someone suggested I wasn't returning the right value, however i'm not sure what is meant by that.

Please let me know if there is any confusion.

I'm only interested in leaf nodes and the way i generate my tree is that ill always have both a left_child and right_child and they will be NULL when initialised. So checking if theres a left_child is enough for me to verify its a leaf node. — james liu
– james liu, Commented Apr 28, 2021 at 13:01
Those recursive dives still return something, you know. Perhaps you should retain that rather than just set it up to ignore it. I also see zero point in passing address in this function. You only use it as an assignment target and, being a value parameter, it is ultimately worthless, since that reaping is lost anyway once the function returns. — WhozCraig
– WhozCraig, Commented Apr 28, 2021 at 13:05
are u looking for the first in-order node that satisfies those conditions? — tstanisl
– tstanisl, Commented Apr 28, 2021 at 13:11
@WhozCraig Yep I agree, there was no reason to pass address, it was merely something left over from an old solution i tried. I tried to have void* address; uninitialised in my main. Then pass it into this function and instead of returning void* i would instead have void, I would access it in my main after it had been initialised in this function. — james liu
– james liu, Commented Apr 28, 2021 at 13:17

tstanisl · Accepted Answer · 2021-04-28 13:20:57Z

2

I guess that the problem might be caused by using a function parameter address that behaves like a local variable. Thus modifications of address are not visible with context of other recursive calls.

I suggest not using this argument. Just return the results when the first node satisfying the conditions is found.

void *inorder_traversal(void *heapstart, uint32_t size)) {
    struct node *head = (struct node* )heapstart;
    if (head->left_child == NULL) {
        if (condition1) {
            if (condition2) {
                return head->address;
            }
        }
        // this branch is empty
        return NULL;
    }
    // try left child, if it fails then try the right one
    void *address = inorder_traversal(head->left_child, size);
    if (address) return address;
    return inorder_traversal(head->right_child, size);
}

answered Apr 28, 2021 at 13:20

tstanisl

14.3k3 gold badges31 silver badges45 bronze badges

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

2 Comments

james liu Over a year ago

Thanks for the suggestion, Ill see if i can make it work.

james liu Over a year ago

This solution with some tweaks was everything i needed to get it to work. Makes so much sense in hindsight. Thanks you!

Ian Abbott · Accepted Answer · 2021-04-28 14:39:01Z

In-order traversal is supposed to (recursively) visit the nodes in the order: node's left sub-tree, the node itself, the node's right sub-tree.

It is not clear what OP's inorder_traversal function is supposed to return if none of the nodes satisfy the condition, so I will assume it should return NULL.

I have omitted the address parameter from my version of the inorder_traversal function below since it is not used.

void *inorder_traversal(void *heapstart, uint32_t size)
{
    struct node *head = heapstart;
    void *address;

    /* Deal with empty sub-tree. */
    if (head == NULL) {
        return NULL;
    }
    /* Check the left sub-tree for a suitable address. */
    address = inorder_traversal(head->left_child, size);
    if (address == NULL) {
        /* Check the head for a suitable address. */
        if (condition1) {
            if (condition2) {
                address = head->address;
            }
        }
    }
    if (address == NULL) {
        /* Check the right sub-tree for a suitable address. */
        address = inorder_traversal(head->right_child, size);
    }
    return address;
}

Collectives™ on Stack Overflow

Returning a value in recursion

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related