У меня есть следующий рекурсивный код, и я получаю stackoverflow исключение. Я не могу выяснить первопричину, потому что, после того как я получаю исключение, я не получаю полный стек вызовов в Visual Studio.
Идея состоит в том, что существуют org команды, которые свертываются в более многочисленные "Основные" команды.
Кто-либо видит, что дефект на этом коде ниже этого мог быть преступником?
private Unit GetUnit(Unit organisationalUnit)
{
if (organisationalUnit.IsMainUnit)
{
return organisationalUnit;
}
if (organisationalUnit.Parent == null)
return null;
return GetUnit(organisationalUnit.Parent);
}
Всегда ли корень имеет Parent == null
?
Пробовали проверить
if (organisationalUnit.Parent == organisationalUnit)
return null;
?
IsMainUnit
и Parent
не вызывают GetUnit
. Я мало что знаю о visual studio. Но вы должны проверить повторение. например
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);
}
Вы можете попробовать это, чтобы лучше отладить. Это не повлияет на ваш производственный код.
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;
Вы можете попробовать передать набор предыдущих посещенных узлов и проверить, посещали ли вы этот узел раньше.
Фишка рекурсии в том, что вы должны быть уверены, что она закончится, а непроверенная круговая ссылка - это ситуация, когда она не закончится.
Есть ли причина не перекодировать его как итерацию? Таким образом, было бы проще установить жесткое ограничение глубины организационного дерева, чтобы улавливать неверные (циклические) данные.
Рекурсия - это весело, и хвостовая оптимизация может даже сделать ее эффективной, но здесь она кажется большим молотком для небольшой проблемы.
Я думаю, что вы можете избежать рекурсии, переписав это следующим образом
while(organisationalUnit!=null && !organisationalUnit.IsMainUnit)
organisationalUnit=organisationalUnit.Parent;
return organisationalUnit;
Надеюсь, это поможет.
EDIT: Я только что понял, что это все равно не сработает, если у вас есть какая-то циклическая зависимость.
Код выглядит нормально, возможно, у вас есть несколько закрытых циклов в дереве Unit? Попробуйте добавить линии трассировки со значениями organisationalUnit.GetHashCode, вывод трассировки не ограничен и может помочь обнаружить причину переполнения стека.
Один из способов сделать это - уменьшить размер стека, чтобы он мог дать сбой раньше.
Вы можете сделать это, потратив впустую кадров в начале программы, т.е. получить трассировку стека, например: f_n, f_ (n-1), ..., f_1, отходы, отходы, ..., отходы, как в (в псевдокоде C)
int wasted = 1;
отходы (int n, void (* f) ()) {если (n> 0) отходы (n - 1, f) else f (); потрачено впустую + = 1; }
main () {отходы (N, mainprime); }
где mainprime - ваш старый main, а N достаточно велик, чтобы достичь желаемого f_1.
У вас может быть цикл в вашем графе (видите, это не дерево).
Для его обнаружения можно использовать код вроде этого:
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);
}