Recursion algorithms: suggested patterns and practices?

Question

I am writing a utility that reflects on two object graphs and returns a value to indicate whether the graphs are identical or not. It got me thinking, is there a generally accepted pattern for writing a recursion algorithm that returns a value from some where in the recursion?

My solution would probably use a ref parameter and look something like this pseudo code:

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

Is there a better / cleaner / more efficient way? Is there a general pattern for such a function?

Answer 1

I've always been a fan of having an actual return value from a recursive function, not just passing in a reference to a variable. I[m not really sure what you're trying to do in your sample, but why not just return a bool from CheckChanged?

Answer 2

I don't see any benefits of your version when compared to this highly trivial version:

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

As an added benefit, some compilers are able to use tail call optimization to turn this version into a simple loop, which is more effective.

Answer 3

There is no general pattern for recursive functions. The only requirement is that the function is guaranteed to reach a degenerate (i.e. non-recursive) case, so you don't end up with infinite recursion. Generally speaking, using a return value is probably slightly more efficient than passing a pointer parameter, but this will depend on the specific problem and the compiler used.

In any case, such micro-optimizations are rarely helpful. Focus on getting the best runtime complexity first, and then tweak the code later if you end up with a performance problem.

Answer 4

Tail recursion isn't just more effective, it keeps you from blowing out the stack on deep recursion: http://en.wikipedia.org/wiki/Tail_recursion

That is to say, it prevents "Stack Overflow" :)

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