I am not used to writing recursive but never had a similar issue before.

In C# I have a recursive method that has a clear base case: when all sets of colors are replaced exit and add that one to the final result. Here is my code

private void ColorCanBeReplacedRecursively(
    IList<IGrouping<string, Element>> userColorBag,
    IList<IGrouping<string, Element>> setColorBag)
{
    if (setColorBag.Count == 0) // if all color groups are replaced
    {
        return;
    }

    foreach (var setColor in setColorBag)
    {
        var futureSetColorBag = new List<IGrouping<string, Element>>();
        futureSetColorBag.AddRange(setColorBag);

        for (var i = 0; i < userColorBag.Count; i  )
        {
            var futureUserColorBag = new List<IGrouping<string, Element>>();
            futureUserColorBag.AddRange(userColorBag);

            var userHasAllPieces = HasUserAllSetPiecesInSpecificColor(userColorBag[i], setColor);
            if (userHasAllPieces)
            {
                futureUserColorBag.RemoveAll(u => u.Key.Equals(userColorBag[i].Key));
                futureSetColorBag.RemoveAll(s => s.Key.Equals(setColor.Key));

                ColorCanBeReplacedRecursively(futureUserColorBag, futureSetColorBag);
            }

        }
    }
}

and here is how I call the recursive method for the first

    foreach (var set in caseSets)
    {          
        ColorCanBeReplacedRecursively(userGroupBy, setGroupBy);
        _expandedSets.Add(set);
    }

After some recursion the count of futureSetColorBag becomes 0, it even enters the if(count==0) but the problem is the return doesn't exit the recursive method entirely. It goes back in the loop and setColorBag finds some items to iterate one again! What am I doing wrong here?

CodePudding user response：

return only returns from the current call. It will return back to the parent call, which is still in the loop. Returning removes only the topmost call frame from the call stack. All other call frames are unaffected. That's how recursion works :)

If you want to unwind your complete stack, you have to return something from your method (such as a boolean) and then use this return value at the call-site to decide if you want to return too (and then return from the calling caller, return from the calling calling caller, and so on).

Something like this (pseudo code):

boolean Recurse(object param)
{
  if (abort)
  {
    return true;
  }

  foreach (var item in items)
  {
    if (Recurse(param))
    {
      return true;
    }
  }

  return false;
}