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

Question

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

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

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

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

Answer 3

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

В любом случае такие микроуправки редко помогают. Сосредоточьтесь на том, чтобы сначала получить наилучшую сложность выполнения, а затем настроить код позже, если у вас возникнет проблема с производительностью.

Answer 4

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

То есть, она не позволяет «Переполнение стека» :)

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