Returning a value in recursion

user_15771325 0
Viewed 66

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.

pointers recursion c
2 Answers

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);
}
user_49894510

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;
}
user_52644910
Related