Stackoverflow exception occurs while trying to get all combinations from two arrays

Question

I am trying to get all combinations from int[] prices and int[] volumes. The two arrays are of the same size each item in prices have an analogous volume in volumes, I want to create list of lists to represent a collection of size (numberOfItemsInCollection) and the sum of prices and volumes for each collection. each collection must be like the following (item1, item2,.., item(n), sumPrices, sumVolumes) so that I can use the sums in further calculations and comparisons.

I used the code like the following and a stack over flow exception occurs

public static void Permute(int[] prices, int[] volumes, int numberOfItemsInCollection, int k, List<int> curr, int sumPrice, int sumVolume,List<List<int>> ans)
{
    if (curr.Count == numberOfItemsInCollection)
    {
        curr.Add(sumPrice);
        curr.Add(sumVolume);
        ans.Add(new List<int>(curr));
        sumPrice = 0;
        sumVolume = 0;
        return;
    }

    for (int i = k; i < prices.Length; i++)
    {
        curr.Add(prices[i]);
        sumPrice+=prices[i];
        sumPrice+=volumes[i];
        Permute(prices, volumes, numberOfItemsInCollection, i, curr,sumPrice, sumVolume, ans);
        curr.RemoveAt(curr.Count - 1);
    }
}

public static List<List<int>> Permute(int[] prices, int[] volumes, int numberOfItemsInCollection)
{
    List<List<int>> ans = new List<List<int>>();
    Permute(prices, volumes, numberOfItemsInCollection, 0, new List<int>(),0,0, ans);
    return ans;
}

Answer 1

Recursion should halt when curr.Count == numberOfItemsInCollection. As far as I can tell curr.Count should increase by one for each level in the recursion tree, i.e. it should be equal to the recursion depth. So the maximum recursion depth should be equal to numberOfItemsInCollection.

So as far as i can see this is a case of infinite recursion. I would estimate one stack frame to take about 60 bytes, so with a 4Mb stack size you should fit about 50k stack frames. So a important question is, how large is numberOfItemsInCollection ? If it is larger than around 1k it might be better to rewrite your algorithm to use iteration with an explicit stack rather than using recursion.

A good way to find out the problem yourself is to debug your program. Eric Lippert has a good article on how to debug small programs. Debugging recursion errors can be a little bit more complicated, but I think visual studio has fairly good tools that should allow you to check if parameters change for each call in a way that should reach the terminating condition.

You might also consider replacing your List<int> curr parameter with a stack, since it seem to be used that way.