Алгоритмы рекурсии: предлагаемые модели и практики?

Question

Я пишу утилиту, которая отображает два графа объектов и возвращает значение, указывающее, идентичны ли графики или нет. Это заставило меня задуматься, есть ли общепринятый шаблон написания алгоритма рекурсии, который возвращает значение из некоторого места в рекурсии?

Мое решение, вероятно, будет использовать параметр ref и выглядеть примерно так: псевдокод:

public static bool IsChanged(T current, T previous)
{
    bool isChanged = false;           
    CheckChanged(current, previous, ref isChanged);          
    return isChanged ;
}


private static void CheckChanged(T current, T previous, ref isChanged)
{
    //perform recursion
    if (graphIsChanged)
       isChanged = true;
    else
       CheckChanged(current, previous, ref isChanged);
}

Есть ли лучший / чище / более эффективный способ? Есть ли общий шаблон для такой функции?

Answer 1

Я не вижу никаких преимуществ вашей версии по сравнению с этой тривиальной версией:

public static bool IsChanged(T current, T previous)
{
    //perform recursion
    if (graphIsChanged)
       return true;
    else
       return IsChanged(current, previous);
}

Как дополнительное преимущество, некоторые компиляторы могут использовать оптимизацию хвостового вызова, чтобы превратить эту версию в простой цикл, который более эффективен.

Answer 2

Хвостовая рекурсия не просто более эффективна, она удерживает вас от раздувания стека при глубокой рекурсии: http://en.wikipedia.org/wiki/Tail_recursion

То есть предотвращает переполнение стека:)

http://en.wikipedia.org/wiki/Stack_overflow

Answer 3

Я всегда любил иметь реальное возвращаемое значение из рекурсивной функции, а не просто передавать ссылку на переменную. Я не совсем уверен, что вы пытаетесь сделать в своем образце, но почему бы просто не вернуть bool из CheckChanged?