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?

andri · Accepted Answer · 2009-06-02 17:44:09Z

6

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.

answered Jun 2, 2009 at 17:44

andri

11.3k2 gold badges40 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

flesh Over a year ago

thanks .. i cant actually use it in my case because the final call is conditional depending on the form of current and previous.. but a nice answer and example anyway

klochner · Accepted Answer · 2009-06-02 17:55:44Z

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

edited Jun 2, 2009 at 17:55

answered Jun 2, 2009 at 17:50

klochner

8,1451 gold badge35 silver badges45 bronze badges

Comments

Peter Mourfield · Accepted Answer · 2009-06-02 17:41:30Z

0

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?

answered Jun 2, 2009 at 17:41

Peter Mourfield

1,8851 gold badge19 silver badges38 bronze badges

Collectives™ on Stack Overflow

Recursion algorithms: suggested patterns and practices?

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related