tail_recursion_to_iteration.c

// Version 1: Recursion. 

node_t *find1(node_t *node, int key) {
    if (!node) {
        return NULL;
    }
    if (key < node->key) {
        return find1(node->left, key);
    } else if (key == node->key) {
        return node;
    } else {
        return find1(node->right, key);
    }
}

// All the recursive calls are in tail position. This means that when the recursion unwinds the calling
// function just forwards the return value without doing additional work before passing it along.
// This means it is equivalent to iteration (without an auxiliary stack).

// Version 2: Wrap infinite loop around body and replace tail calls with in-place updates to arguments.
node_t *find2(node_t *node, int key) {
    for (;;) {
        if (!node) {
            return NULL;
        }
        if (key < node->key) {
            node = node->left;
            key = key;
        } else if (key == node->key) {
            return node;
        } else {
            node = node->right;
            key = key;
        }
    }
}

// Version 3: Replace infinite loop with while loop and remove useless assignments.
node_t *find3(node_t *node, int key) {
    while (node) {
        if (key < node->key) {
            node = node->left;
        } else if (key == node->key) {
            return node;
        } else {
            node = node->right;
        }
    }
    return NULL;
}

// Version 4: Replace multiple exits with one exit.
node_t *find4(node_t *node, int key) {
    while (node && key != node->key) {
        if (key < node->key) {
            node = node->left;
        } else {
            node = node->right;
        }
    }
    return node;
}