Как я могу получить поймать корень исключения стека переполнения на рекурсивный код - PullRequest
Новая
       5

Как я могу получить поймать корень исключения стека переполнения на рекурсивный код

6 голосов
/ 13 июля 2010

У меня есть следующий рекурсивный код, и я получаю исключение stackoverflow. Я не могу понять основную причину, потому что как только я получаю исключение, я не получаю полный стек вызовов в Visual studio.

Идея состоит в том, что есть команды оргкомитета, которые объединяются в более крупные "главные" команды.

Кто-нибудь видит недостаток в этом коде ниже, который может быть виновником? 

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

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

        return GetUnit(organisationalUnit.Parent);
    }

Ответы [ 9 ]

5 голосов
/ 13 июля 2010
  1. Возможно, у вас есть юнит, который является его собственным родителем, или вы можете запретить ему иметь круг родителей (например, A-B-C-A). То есть проблема может быть связана с данными, а не с самим кодом.
  2. Убедитесь, что получатели IsMainUnit и Parent не вызывают GetUnit.
4 голосов
/ 13 июля 2010

Всегда ли в корне Parent == null? Пробная проверка 

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

2 голосов
/ 13 июля 2010

Вы можете попробовать это отладить лучше.Это не повлияет на ваш производственный код. 

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

Если подумать ...

Скорее всего, у вас где-то есть циклическая ссылка. 

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

Выможет попытаться передать набор предыдущих посещенных узлов и проверить, посещали ли вы этот узел ранее или нет.

С recursion дело в том, что вы должны быть уверены, чтооно закончится , а неконтролируемая циклическая ссылка - это ситуация, в которой оно не закончится.

1 голос
/ 13 июля 2010

Один из способов сделать это - уменьшить размер стека, чтобы он мог произойти раньше.

Вы можете сделать это, потратив фреймов на начало программы, то есть получить трассировку стека, например: f_n, f_ (n-1), ..., f_1, ненужные, ненужные, ..., отходы, как в (в псевдокоде C)

int впустую = 1;

отходы (int n, void (* f) ()) {если (n> 0) отходы (n - 1, f), то еще f (); впустую + = 1; }

main () {ненужные (N, mainprime); }

где mainprime - это ваш старый main, а N достаточно большой, чтобы достичь желаемого f_1.

1 голос
/ 13 июля 2010

Я не знаю много о визуальной студии. Но вы должны проверить на повторение. например, 

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);
}
1 голос
/ 13 июля 2010

Есть ли причина не перекодировать его как итерацию?Таким образом, было бы проще установить жесткий предел для глубины организационного дерева, чтобы собирать неверные (циклические) данные.

Рекурсия - это весело, и оптимизация хвоста может даже сделать ее эффективной, но здесь она кажется большим молотком для небольшой проблемы.

0 голосов
/ 13 июля 2010

Возможно, на вашем графике есть цикл (видите, это не дерево).

Вы можете использовать такой код, чтобы обнаружить его: 

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);
}
0 голосов
/ 13 июля 2010

Я полагаю, что вы могли бы избежать рекурсии, переписав это в соответствии с 

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

return organisationalUnit;

Надеюсь, это поможет.

РЕДАКТИРОВАТЬ: я только что понял, что это все равно не получится, если у вас есть какая-то циклическая зависимость.

0 голосов
/ 13 июля 2010

Код выглядит хорошо, может быть, у вас есть несколько замкнутых циклов в дереве модулей? Попробуйте добавить линии трассировки со значениями organisationalUnit.GetHashCode, вывод трассы не ограничен и может помочь обнаружить причину переполнения стека.

...