Change recursion to iteration

Change recursion to iteration

Recursion is an elegant method of problem solution, but often incurs unnecessary function call overhead. Where possible, recursion should be replaced with an iterative algorithm. For example, the famous example of a recursive “factorial” function would always be coded in a loop by professional programmers.

Fibonacci numbers. With a little insight, many recursive algorithms can be coded without recursion. For example, the Fibonacci number sequence (1,1,2,3,5,8,13,...) is defined by having the next number as the sum of the previous two numbers, with the following recursive rules:

    Fib(0) = 1
    Fib(1) = 1
    Fib(n) = Fib(n−1) + Fib(n−2)

This has the obvious and very elegant recursive implementation:

    int fibonacci(int n)
    {
        if (n <= 1 )
            return 1;
        else
            return fibonacci(n - 1) + fibonacci(n - 2);
    }

However, there is no need to use recursion here, and a short loop is adequate. A non-recursive computation of the Fibonacci numbers is shown below:

    int fibonacci(int n)
    {
        int small = 1, large = 1;  // F0 = F1 = 1
        while (n > 1) {
            int temp = small + large; // Fn = Fn-1 + Fn-2
            small = large;
            large = temp;
            n--;
        }
        return large;
    }

Binary Trees. There are many examples of common algorithms that are unnecessarily coded using recursion. Almost all linked list algorithms can be coded without recursion, as can the most common binary search tree operations: search, insertion and deletion. For example, the recursive implementation of tree insertion is:

    void insert(Tree *root, Tree new_node)
    {
        if (*root == NULL) // Found bottom of tree 
            *root = new_node; // insert here 
        else {
            if (new_node->data <= (*root)->data)
                insert(&(*root)->left, new_node);
            else
                insert(&(*root)->right, new_node);
        }
    }

The non-recursive version of binary tree insertion is given below. It is somewhat less elegant, uses a few more variables, but should be more efficient.

    void insert(Tree *root, Tree new_node)
    {
        Tree temp = *root;
        if (temp == NULL) // empty tree special case
            *root = new_node;
        else {
            for (;;) {
                if (new_node->data <= temp->data) { // go left?
                    if (temp->left == NULL) { // leaf?
                        temp->left = new_node; // insert it
                        return; // finished
                    }
                    else
                        temp = temp->left; // go left
                }
                else { // going right
                    if (temp->right == NULL) { // leaf?
                        temp->right = new_node; // insert it
                        return; // finished
                    }
                    else
                        temp = temp->right; // go right
                }
            }
        }
    }

I'm sorry, Professor! Your recursive code is short and beautifully elegant, but mine is longer, uglier, and faster! Maybe I shouldn't tell my Professor that I've never coded a binary tree since finishing my degree? Hash tables are the name of the game.

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++