Rewrite recursion within loop to use only loops

Question

I am sitting now for a few hours on the following problem, I have a code, that calculates how many boxes fit in a package. For that I calculate package per package and check box for box.

Here is the code:

private bool CalculateOnePackage(Package package, List<Item> workItems, List<Item> packagedItemsList)
{
  if (workItems.Count == 0)
  {
    return true;
  }

  var packages = new List<Package>();
  Item tempItem = null;
  foreach (Item entity in workItems)
  {
    if (/* execude code that changes entity and packages */)
    {
      tempItem = entity;
      break;
    }
  }

  if (tempItem == null)
  {
    return false;
  }

  packagedItemsList.Add(tempItem);
  workItems.Remove(tempItem);

  foreach (var p in packages)
  {
    this.CalculateOnePackage(p, workItems, packagedItemsList);
  }

  return true;
}

How can I rewrite the code to only use loops? We have the problem, that this code causes a StackoverflowException.

use for loop with break when you reach your maximum limit of boxes in a package break the loop if you understand this then i will post the code as well — rashfmnb, Apr 14 '16 at 12:26
by the sounds of it then, you're looping over all packages including the package you're already in.. — BugFinder, Apr 14 '16 at 12:26
You could use the [`Queue<`-class](https://msdn.microsoft.com/en-us/library/7977ey2c(v=vs.110).aspx) to avoid the `StackOverFlowException`. Therefore add the packages to the queue, process it and remove it from it. Loop the queue while `queue.Count > 0` — Tim Schmelter, Apr 14 '16 at 12:27
@BugFinder To be honest, it is not my code and for me it looks like I described it. The only thing I am supposed to do is, to replace the recursion by a loop. So I cannot answer detail questions :( — Knerd, Apr 14 '16 at 12:37
@TimSchmelter the idea with the Queue is nice, do you have an example? — Knerd, Apr 14 '16 at 12:37
Well the forloop could end up with the same problem if you dont exclude the package you started with. think about it, lets give it just a number so it starts at say 1 of 50, so you kick off the first package with calculateonepackage(1) .. so it goes in, and sends calculateonepackage(1) which goes in and sends calculateonepackage(1)....... till you blow your stack — BugFinder, Apr 14 '16 at 12:38
Possible duplicate of [how to rewrite a recursive method by using a stack?](http://stackoverflow.com/questions/7293406/how-to-rewrite-a-recursive-method-by-using-a-stack) — MicroVirus, Apr 14 '16 at 12:40
Well the recursion causes a stack overflow because you get a parameter combination that actually never causes your exit conditions to be true. Without seeing more of the code it's hard to say though why and also what exactly you're trying to accomplish. — Adwaenyth, Apr 14 '16 at 12:41
@MicroVirus the linked question doesn't have a recursion in a loop. — Knerd, Apr 14 '16 at 12:41
@Adwaenyth ok, I gonna add some code to show the exit conditions. — Knerd, Apr 14 '16 at 12:42
Just look at the answer, the second part which discusses non-tailrecursive algorithms and rewrites it to a stack-based solution. The fact that you have a loop simply means that you push each item which you loop over onto the stack, rather than just one item. Other than that minor change in specifics, it's the same type of rewrite. — MicroVirus, Apr 14 '16 at 12:43
You never add something to the `List`. Strange code. I'd show a `Queue` example but it's difficult because i don't understand what your method is supposed to do. — Tim Schmelter, Apr 14 '16 at 12:48
Your sample code is also equivalent to running through a directory tree. See [this MSDN article](https://msdn.microsoft.com/en-us/library/bb513869.aspx?f=255&MSPPError=-2147217396) which in great detail shows the recursive versus the stack-based solution. Regarding your updated code, I'm with @TimSchmelter here... it doesn't make any sense. — MicroVirus, Apr 14 '16 at 12:49
@TimSchmelter I was still answering on the original question without the specifics for the code; the current code doesn't make a whole lot of sense. — MicroVirus, Apr 14 '16 at 12:52
It's still too unclear, you need to know exactly what you are recursing over. From what I can tell, you recurse over the packages which are nested in other packages (?), whilst updating `workItems` into `packedItemsList`? — MicroVirus, Apr 14 '16 at 12:58
Your `packages` list is still very much empty, so your code doesn't even reach the recursive call - unless that `if` statement in the `workItems` loop adds something to the `packages` list. — Adwaenyth, Apr 14 '16 at 13:02
@Adwaenyth yeah, the method call in the if statement adds items to `packages` — Knerd, Apr 14 '16 at 13:07
@Knerd This could be the crucial point though. If you add all but one of your original items there (worst case) then the recursive call could end up to be executed `(n-1)!` times - n being the number of `workItems`. — Adwaenyth, Apr 14 '16 at 13:11

score 1 · Answer 1 · answered Apr 14 '16 at 12:59

You could use the Queue<-class to avoid the StackOverFlowException. Therefore add the packages to the queue, process it and remove it from it afterwards. Loop the queue while queue.Count > 0.

Since i don't know what the method is supposed to do it's difficult to show a good example. Perhaps (replacing also your loop with a simple LINQ query):

private void CalculateOnePackage(Package package, List<Item> workItems)
{
    Queue<Package> packages = new Queue<Package>();
    packages.Enqueue(package);

    while (packages.Count > 0)
    {
        // method ProcessEntity adds package(s) to the queue
        Item entityItem = workItems
            .FirstOrDefault(item => ProcessEntity(item, packages)); 
        // do something with it if entityItem != null
    }
}

score 0 · Answer 2 · answered Apr 14 '16 at 12:58

Write something like that, but at first you should debug and fix returns. Also, your function doesn't use Package package.

Moreover, your function doesn't use results of inner recursion calls. (It doesn't return or use this.CalculateOnePackage(p, workItems, packagedItemsList);). After I've realized it, I stopped my attempts to rewrite your code. But you can read my uncomplete result below:

private bool CalculateOnePackage(Package package0, List<Item> workItems0, List<Item> packagedItemsList0)
    {
        var q = new Queue<Tuple<Package, List<Item>, List<Item>>>();
        q.Enqueue(new Tuple<Package, List<Item>, List<Item>>(package0, workItems0, packagedItemsList0));
        while (q.Count != 0)
        {
            var state = q.Dequeue();
            var package = state.Item1;
            var workItems = state.Item2;
            var packagedItemsList = state.Item3;

            if (workItems.Count == 0)
            {
                return true;
            }

            var packages = new List<Package>();
            Item tempItem = null;
            foreach (Item entity in workItems)
            {
                if (/* execude code that changes entity */)
                {
                    tempItem = entity;
                    break;
                }
            }

            if (tempItem == null)
            {
                return false;
            }

            packagedItemsList.Add(tempItem);
            workItems.Remove(tempItem);

            foreach (var p in packages)
            {
                q.Enqueue(new Tuple<Package, List<Item>, List<Item>>(p, workItems, packagedItemsList));
            }
        }


        return true;
    }

Rewrite recursion within loop to use only loops

2 Answers2