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
– rashfmnb, Commented Apr 14, 2016 at 12:26
by the sounds of it then, you're looping over all packages including the package you're already in.. — BugFinder
– BugFinder, Commented Apr 14, 2016 at 12:26
You could use the Queue<<T>-class 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
– Tim Schmelter, Commented Apr 14, 2016 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
– Knerd, Commented Apr 14, 2016 at 12:37
You never add something to the List<Package>. Strange code. I'd show a Queue<Package> example but it's difficult because i don't understand what your method is supposed to do. — Tim Schmelter
– Tim Schmelter, Commented Apr 14, 2016 at 12:48

Tim Schmelter · Accepted Answer · 2016-04-14 12:59:54Z

1

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
    }
}

answered Apr 14, 2016 at 12:59

Tim Schmelter

462k79 gold badges719 silver badges980 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Schullz · Accepted Answer · 2016-04-14 12:58:59Z

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;
    }

Collectives™ on Stack Overflow

Rewrite recursion within loop to use only loops

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related