how can i get catch the root of a stackoverflow exception on recursive code

Question

I have the following recursive code and i am getting a stackoverflow exception. I can't figure out the root cause because once i get the exception,i dont get the full call stack in Visual studio.

The idea is that there are org teams that roll up into larger "Main" teams.

Does anyone see a flaw on this code below that could be the culprit?

    private Unit GetUnit(Unit organisationalUnit)
    {
        if (organisationalUnit.IsMainUnit)
        {
            return organisationalUnit;                
        }

        if (organisationalUnit.Parent == null)
            return null;

        return GetUnit(organisationalUnit.Parent);
    }

Answer 1

Is there any reason not to recode it as an iteration? That way, it'd be easier to set a hard limit on the depth of the organizational tree in order to catch bad (cyclic) data.

Recursion is fun, and tail optimizations can even make it efficient, but here it seems a like large hammer for a small problem.

Answer 2

1. You might have a unit which is its own parent, or barring that you might have a cycle of parents (e.g. A-B-C-A). That is, the problem might be with the data, not with the code per se.
2. Verify that the getters of IsMainUnit and Parent don't call GetUnit.

Answer 3

Does the root always have Parent == null? Tried checking

if (organisationalUnit.Parent == organisationalUnit)
    return null;

?

Answer 4

I don't know much about visual studio. But you should check for recurrence. e.g.

private Unit GetUnit(Unit organisationalUnit)
{
      GetUnit(organisationalUnit, new vector());
}

private Unit GetUnit(Unit organisationalUnit,vector x)
{
    if (organisationalUnit.IsMainUnit)
    {
        return organisationalUnit;                
    }

    if (organisationalUnit.Parent == null)
        return null;

    x.add(this);
    if(x.contains(organisationalUnit.Parent)) throw new Exception("recurrent parent");
    return GetUnit(organisationalUnit.Parent,x);
}

Answer 5

The code looks OK, maybe you have some closed cycles in the Unit tree? Try to add trace lines with organisationalUnit.GetHashCode values, trace output is not limited and can help to detect stack overflow reason.

Answer 6

I guess you could avoid recursion by rewriting this along the lines of

while(organisationalUnit!=null && !organisationalUnit.IsMainUnit)
  organisationalUnit=organisationalUnit.Parent;

return organisationalUnit;

I hope that helps.

EDIT: I just realized this would still fail if you have some sort of cyclic dependency.

Answer 7

One way to do that would be to reduce the stack size so it can crash earlier on.

You could do that by wasting frames upon the beginning of the program, i.e. to get a stack trace like: f_n,f_(n-1),...,f_1,waste,waste,...,waste, as in (in C pseudo-code)

int wasted = 1;

waste(int n,void (*f)()) { if (n > 0) waste(n - 1,f) else f (); wasted += 1; }

main () { waste(N,mainprime); }

where mainprime is your old main, and N is big enough to reach the f_1 you want.

Answer 8

You could try this to debug it better. It won't affect your production code.

using System.Diagnostics;

private Unit GetUnit(Unit organisationalUnit, int depth)
{
    debug.assert(depth < 10, "Reached an unexpected high recursion depth"); 

    if (organisationalUnit.IsMainUnit)
    {
        return organisationalUnit;                
    }

    if (organisationalUnit.Parent == null)
        return null;

    return GetUnit(organisationalUnit.Parent, depth + 1);
}

private Unit GetUnit(Unit organisationalUnit)
{
    return GetUnit(organisationalUnit.Parent, 0);
}

On second thought...

It's mostlikely that you have a circular reference somewhere.

A.parent = B;
B.parent = C;
C.parent = A;

You could try to pass a set of previous visited nodes and check whether or not you've visited this node before.

The thing with recursion is that you have to be sure that it will end and an unchecked circular reference is a situation where it wouldn't end.

Answer 9

You might have a cycle in your graph (see, it's not a tree).

You can use code like this to detect it:

private Unit GetUnit(Unit organisationalUnit) {
  return GetUnit(organisationalUnit, new HashSet<Unit>());
}

private Unit GetUnit(Unit organisationalUnit, HashSet<Unit> visited) {
  if (visited.Contains(organisationalUnit)) {
    throw new Exception("Cycle detected!"); // or just return null if you prefer
  }
  visited.Add(organisationalUnit);

  if (organisationalUnit.IsMainUnit) {
    return organisationalUnit;
  }

  if (organisationalUnit.Parent == null)
    return null;

  return GetUnit(organisationalUnit.Parent, visited);
}