CODEWITHSUNDEEP
algorithmrecursiondesign-patterns
flesh
flesh

Reputation: 23935

Recursion algorithms: suggested patterns and practices?

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?

Upvotes: 0

Views: 513

Answers (3)

klochner
klochner

Reputation: 8125

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

Upvotes: 4

andri
andri

Reputation: 11292

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.

Upvotes: 6

Peter Mourfield
Peter Mourfield

Reputation: 1885

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?

Upvotes: 0

Related Questions