递归算法:建议的模式和实践？

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

我一直热衷于从递归函数中获得实际的返回值，而不仅仅是传递对变量的引用。我真的不确定你想在你的样本中做什么，但是为什么不直接从CheckChanged返回一个bool呢？