08/05/20

Converting Non-Tail Recursion to Iteration

In this article, we are using a specific example to analyze a scenario when the use of recursion can lead to unexpected and disastrous results. And if you find troublesome recursion inside your code, this article will help you avoid negative consequences.

Here's a small task

We’ve got the matrix

Our task is to calculate the maximum number of adjacent elements with the same values. i.e., the program should return the number 4. C# console application is enough to address the challenge.

The recursive solution with comments:

namespace RecurseToIteration
{
    class Program
    {
        // Matrix sizes
        const int m_height = 3;
        const int m_width = 4;

        // Common data the recursion interacts with
        static bool[,] visitMatrix;
        static int[,] valueMatrix;
        static int targetValue;

        static void Main(string[] args)
        {
            // Matrix initialization
            valueMatrix = new int[m_height, m_width]
            {
                {0, 1, 1, 1},
                {0, 1, 3, 3},
                {2, 2, 3, 1}
            };

            // Another matrix which determines which elements are already visited
            visitMatrix = new bool[m_height, m_width];
            
            int maxCount = 0;
            for (int i = 0; i < m_height; i++)
            {
                for (int j = 0; j < m_width; j++)
                {
                    // Iterate over all elements and start recursions for all not yet visited elements
                    if (visitMatrix[i, j] == false)
                    {
                        // Saving target value in static field to simplify recursive method signature
                        targetValue = valueMatrix[i, j];

                        // Receiving value and updating current maximum if necessary
                        int nextCount = RecurseMethod(i, j);
                        maxCount = nextCount > maxCount? nextCount : maxCount;
                    }
                }
            }

            Console.WriteLine($"Max: {maxCount}");
            Console.ReadKey();
        }

        static int RecurseMethod(int h, int w)
        {
            // Recursion exit conditions:
            // 1. Incorrect bounds
            // 2. Element is already visited
            // 3. Element value does not match target one
            if (h < 0 || w < 0 || h >= m_height || w >= m_width
            || visitMatrix[h, w] || valueMatrix[h, w] != targetValue)
            {
                return 0;
            }

            // Setting visit flag for current value and initializing local sum
            visitMatrix[h, w] = true;
            int sum = 1;

            // Recursively visit all elements around increasing local sum
            sum += RecurseMethod(h + 1, w);
            sum += RecurseMethod(h - 1, w);
            sum += RecurseMethod(h, w + 1);
            sum += RecurseMethod(h, w - 1);

            return sum;
        }
    }
}

The result of the program:

The issue

Everything looks fine. For now. Let's increase the matrix size to 100х100 and remove the INITIALIZATION with custom values. Now we have a 100x100 matrix filled with zeros and the program should return the number 10000.

// Matrix sizes
const int m_height = 100;
const int m_width = 100;

...

// Matrix initialization
valueMatrix = new int[m_height, m_width];
/*{
    {0, 1, 1, 1},
    {0, 1, 3, 3},
    {2, 2, 3, 1}
};*/

This is what we get - the stack overflow:

Since the entire matrix is filled with zeros, we need 10,000 nested calls to our recursive function for the desired result. The maximum call stack size is limited to 1 MB, so we don't have enough memory to handle such a recursion.

What should we do in this case?

The solution is to create your own stack and simulate function calls manually, mimicking what the compiler does. In addition, you need to create a helper class and its instances will store the arguments required for operation, as well as the final result for each call.

Let us emphasize the fact that we are not dealing with ordinary tail recursion. In this particular case, the function calls itself 4 times, adding each result to the sum. We need to split our function into numbered blocks, and also introduce a variable that helps to determine from which block execution will continue when the next element is popped from the stack. Let's call it 'state'.

static int RecurseMethod(int h, int w)
{
    // state = 0
    if (h < 0 || w < 0 || h >= m_height || w >= m_width
    || visitMatrix[h, w] || valueMatrix[h, w] != targetValue)
    {
        return 0;
    }

    visitMatrix[h, w] = true;
    int sum = 1;

    sum += RecurseMethod(h + 1, w); // state 1
    sum += RecurseMethod(h - 1, w); // state 2
    sum += RecurseMethod(h, w + 1); // state 3
    sum += RecurseMethod(h, w - 1); // state 4

    return sum; // state 5
}

And here is the structure pushed onto the stack. It stores our coordinates, the total amount, and the block number from which the execution will continue.

class Entry
{
    public int height;
    public int width;
    public int sum = 0;
    public int state = 0;

    public Entry(int height, int width)
    {
        this.height = height;
        this.width = width;
    }
}

The iterative solution with comments:

using System;
using System.Collections.Generic;
using System.Linq;

namespace RecurseToIteration
{
    class Program
    {
        // Matrix sizes
        const int m_height = 100;
        const int m_width = 100;

        // Common data the recursion interacts with
        static bool[,] visitMatrix;
        static int[,] valueMatrix;
        static int targetValue;

        static void Main(string[] args)
        {
            // Matrix initialization
            valueMatrix = new int[m_height, m_width];

            // Another matrix which determines which elements are already visited
            visitMatrix = new bool[m_height, m_width];
            
            int maxCount = 0;
            for (int i = 0; i < m_height; i++)
            {
                for (int j = 0; j < m_width; j++)
                {
                    // Iterate over all elements and start recursions for all not yet visited elements
                    if (visitMatrix[i, j] == false)
                    {
                        // Saving target value in static field
                        targetValue = valueMatrix[i, j];
                        
                        // Receiving value and updating current maximum if necessary
                        int nextCount = IterationMethod(i, j);
                        maxCount = nextCount > maxCount? nextCount : maxCount;
                    }
                }
            }

            Console.WriteLine($"Max: {maxCount}");
            Console.ReadKey();
        }

        class Entry
        {
            public int height;
            public int width;
            public int sum = 0;
            public int state = 0;

            public Entry(int height, int width)
            {
                this.height = height;
                this.width = width;
            }
        }

        static int IterationMethod(int h, int w)
        {
            // Initializing stack explicitly and pushing first element
            Stack stack = new Stack();
            stack.Push(new Entry(h, w));

            while (true)
            {
                // Popping last element
                Entry entry = stack.Pop();
                h = entry.height;
                w = entry.width;

                // Code which gets executed before 4 recursions execution in previous implementation
                if (entry.state == 0)
                {
                    // Checking exit conditions
                    if (h < 0 || w < 0 || h >= m_height || w >= m_width
                    || visitMatrix[h, w] || valueMatrix[h, w] != targetValue)
                    {
                        // “return 0” analogue as sum doesn’t get changed in this case
                        continue;
                    }

                    visitMatrix[h, w] = true;
                    entry.sum = 1;
                }

                // Going to next state
                entry.state += 1;

                // Calculatin next element coordinates depending on current state
                if (entry.state == 1)
                    h++; // RecurseMethod(h + 1, w);
                else if (entry.state == 2)
                    h--; // RecurseMethod(h - 1, w);
                else if (entry.state == 3)
                    w++; // RecurseMethod(h, w + 1);
                else if (entry.state == 4)
                    w--; // RecurseMethod(h, w - 1);
                else
                {
                    // If all elements around are visited then processing final “return”
                    if (stack.Count > 0)
                    {
                        // If stack is not empty then “return the result” by adding current sum to previous element’s one
                        stack.Last().sum += entry.sum;
                        continue;
                    }
                    else
                        // Otherwise we’ve got to the first element and have final result
                        return entry.sum;
                }

                // Creating next stack item with calculated coordinates
                Entry newEntry = new Entry(h, w);

                // And pushing back current element with newly created one
                stack.Push(entry);
                stack.Push(newEntry);
            }
        }
    }
}

Now the result is what it should be.

And here's the result for a 300 × 300 matrix

Conclusion

You can use a recursion, but you need to do it consciously, taking into account the negative consequences and problems that may arise at the production stage and lead to significant costs for your customers.

By: Roman Shaposhnikov