Recursion. Not all code paths return a value

Question

I am sure I am making a foolish mistake here but it beats me. Here is a piece of code:

void Main()
{
    //Key is a parent while the list contains its children
    Dictionary<string,List<string>> d = new Dictionary<string,List<string>>();
    d.Add("1",new List<string>(){"2","3"});//valid.should return false 
    d.Add("2",new List<string>(){"4"});//valid.should return false
    d.Add("3",new List<string>(){"5"});//valid.should return false
    d.Add("4",new List<string>(){"1"});//invalid.should return true 

   IsChildAlreadyAParent("4","2",d);
 }

private bool IsChildAlreadyAParent( string child, string parent, Dictionary<string, List<string>> d )
{           
    if( !d.ContainsKey( child ) || ( d.ContainsKey( child ) && d[child].Count == 0 ))
    {
        return false;
    }

    foreach( string childOfChild in d[child] )
     {
        if( childOfChild == parent )
            return true;

        if( IsChildAlreadyAParent( childOfChild, parent, d ) ) return true;
    }
}

Compiling this gives me this error:

IsChildAlreadyAParent(string, string, System.Collections.Generic.Dictionary<string,System.Collections.Generic.List<string>>)': not all code paths return a value

I have read the code a few times and I cant see how a return condition would be missed. I know I can rectify it by adding a method return statement before the method end but it doesn't help me understand the issue at hand. Where is the gap??

Ben Voigt · Accepted Answer · 2012-01-13 00:35:56Z

6

You might think this executes the loop body exactly once, always returning from the function:

foreach( string childOfChild in d[child] )
{
    if( childOfChild == parent )
        return true;

    return IsChildAlreadyAParent( childOfChild, parent, d );
}

But what if d[child] has no elements at all?

Also, testing only the first child probably isn't the right solution either.

Better:

foreach( string childOfChild in d[child] )
{
    if( childOfChild == parent ) return true;
    if (IsChildAlreadyAParent( childOfChild, parent, d )) return true;
}
return false;

answered Jan 13, 2012 at 0:35

Ben Voigt

286k45 gold badges444 silver badges764 bronze badges

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

3 Comments

umbersar Over a year ago

modified the code to handle that as well...still the same issue and i dont wan't to use a method return at the end as u have done here..

umbersar Over a year ago

but the point that is raised, "testing only the first child probably isn't the right solution either", was helpful

Ben Voigt Over a year ago

@wanderer: Sorry, the compiler isn't smart enough to notice that you've already tested for an empty list. So it still is concerned with what happens below the loop.

JaredPar · Accepted Answer · 2012-01-13 00:52:18Z

2

The compiler is complaining because in the case where the d[child] collection is empty the loop body will never run. There is no return on that particular code path and hence you get an error.

Additionally your version of the code will lookup child in the dictionary 3 times on a successful execution. You could optimize this to only do one lookup with TryGetValue.

Here's the code with a couple of fixes

private bool IsChildAlreadyAParent(
  string child, 
  string parent, 
  Dictionary<string, List<string>> d )
{           
    List<string> list;
    if (!d.TryGetValue(child, out list) || list.Count == 0)
    {
        return false;
    }

    if (list[0] == parent)
    {
      return true;
    }

    return IsChildAlreadyAParent(list[0], parent, d );
}

edited Jan 13, 2012 at 0:52

answered Jan 13, 2012 at 0:40

JaredPar

759k152 gold badges1.3k silver badges1.5k bronze badges

3 Comments

JaredPar Over a year ago

@wanderer my bad, fixed the typo. Should compile now

JaredPar Over a year ago

@wanderer yes, but that's how your original sample functioned. The loop only ever did a single iteration. It either matched parent or it immediately called into IsChildAlreadyAParent with effectively list[0].

umbersar Over a year ago

@jaredpar....my fault..sorry. was a mistake...i wanted to iterate the complete list checking for the condition.

gorootde · Accepted Answer · 2012-01-13 00:36:19Z

0

What if d[child] has a length of 0? So your for-loop won't run -> no return value

answered Jan 13, 2012 at 0:36

gorootde

4,1134 gold badges46 silver badges87 bronze badges

Comments

Aleksandar Vucetic · Accepted Answer · 2012-01-13 00:36:29Z

0

It might happen that your code never gets into "foreach"...you should have return at the end...if d[child] doesn't have elements at all...

answered Jan 13, 2012 at 0:36

Aleksandar Vucetic

15k9 gold badges56 silver badges56 bronze badges

Comments

Keith Nicholas · Accepted Answer · 2012-01-13 00:37:06Z

0

well, what if your list is empty?

Not to mention the foreach loop is pointless. It will always terminate on the first iteration.

answered Jan 13, 2012 at 0:37

Keith Nicholas

44.4k15 gold badges101 silver badges168 bronze badges

Collectives™ on Stack Overflow

Recursion. Not all code paths return a value

5 Answers 5

3 Comments

3 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related