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.