CODEWITHSUNDEEP
c#recursion
Knerd
Knerd

Reputation: 2002

Rewrite recursion within loop to use only loops

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.

Upvotes: 0

Views: 112

Answers (2)

Tim Schmelter
Tim Schmelter

Reputation: 460098

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

Upvotes: 1

Schullz
Schullz

Reputation: 283

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

Upvotes: 0

Related Questions