There are a few programming problems that can be solved using more than one style. For example - Print all combinations of size r in an array of size n. It can be solved using at least 2 approaches - a recursive approach and an iterative approach.
While you can understand the fundamental approach of breaking the problem into repeated problem with a reduced data set, goal here is to compare their runtime durations.
Recursive
private static void PrintCombinationRecursive(int[] arr, int size) {
List<List<int>> output = new List<List<int>>();
Helper(arr, size, 0, arr.Length - 1, new List<int>(), output);
Console.WriteLine($"PrintCombinationRecursive-count:{output.Count}");
}
private static void Helper(int[] arr, int size, int start, int end, List<int> currentList, List<List<int>> finalList) {
if (start > end) {
if (currentList.Count == size) {
finalList.Add(Clone(currentList));
}
return;
}
Helper(arr, size, start + 1, end, Clone(currentList), finalList);
currentList.Add(arr[start]);
Helper(arr, size, start + 1, end, Clone(currentList), finalList);
}
private static List<int> Clone(List<int> items) {
var newList = new List<int>();
foreach (var item in items) {
newList.Add(item);
}
return newList;
}
Iterative
private static void PrintCombinationIterative(int[] arr, int size) {
if (arr.Length < size) {
return;
}
Queue<List<(int, int)>> queue = new Queue<List<(int, int)>>();
int i = 0;
int counter = 0;
foreach (var val in arr) {
queue.Enqueue(new List<(int, int)> { (val, i) });
i++;
}
while (queue.Count > 0) {
var item = queue.Dequeue();
if (item.Count < size) {
var last = item[item.Count - 1];
if (last.Item2 >= arr.Length - 1) {
continue;
}
var clone = Clone(item);
item.Add((arr[last.Item2 + 1], last.Item2 + 1));
queue.Enqueue(item);
clone[clone.Count - 1] = (clone[clone.Count - 1].Item1, clone[clone.Count - 1].Item2 + 1);
queue.Enqueue(clone);
}
else {
counter++;
}
}
Console.WriteLine($"PrintCombinationIterative-count:{counter}");
}
private static List<(int, int)> Clone(List<(int, int)> items) {
List<(int, int)> newList = new List<(int, int)>();
foreach (var item in items) {
newList.Add(item);
}
return newList;
}
Driver code
int[] arr = new int[20] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
int r = 2;
for (int i = 0; i < 3; i++)
{
Stopwatch sw = Stopwatch.StartNew();
PrintCombinationRecursive(arr, r);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
}
for (int i = 0; i < 3; i++)
{
Stopwatch sw = Stopwatch.StartNew();
PrintCombinationIterative(arr, r);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
}
Output
PrintCombinationRecursive-count:190
268
PrintCombinationRecursive-count:190
235
PrintCombinationRecursive-count:190
217
PrintCombinationIterative-count:190
4
PrintCombinationIterative-count:190
0
PrintCombinationIterative-count:190
0
Conclusion
Allocating stacks for function calls during recursive calls add to the time taken to complete the code logic. Iterative code is more efficient. Point to note is that runtime complexity is about the same.
