Recursion problem

**deltanosix** · 02-02-2012

Hello,

I'm running a binary search using recursion, and I keep getting a segmentation fault. Here is the part of the code that doesn't seem to be working, can anyone tell me why? Thanks for the help!

Code:

bool
sort2(int value1, int array1[], int high, int low)
{
    int middle = (low + high) / 2;
    if(value1 < array1[middle]) {
        high = middle - 1;
        sort2(value1, array1, high, low);
    }
    if(value1 > array1[middle]) {
        low = middle + 1;
        sort2(value1, array1, high, low);
    }
    if (value1 == array1[middle]) 
        return true;

return false;
}

**stahta01** · 02-02-2012

Added fix and clarity re-write. Note: did not compile or test code.
You did NOT have ending condition for item not in array.

Note: Code still has original lack of return on recursive function.

Tim S.

Code:

bool sort2(int value1, int array1[], int high, int low)
{
    int middle = (low + high) / 2;
    if (value1 == array1[middle]){
        return true;
    } else if( low == high {
        return false;
    } else if(value1 < array1[middle]) {
        high = middle - 1;
        sort2(value1, array1, high, low);
    } else if(value1 > array1[middle]) {
        low = middle + 1;
        sort2(value1, array1, high, low);
    }
}

**laserlight** · 02-02-2012

Are you sure that you are handling the case of an element not being found correctly?

Also, since "sort2" (horrible name for a function that does binary search) returns a value, your recursive calls of sort2 should have their values returned.

**anduril462** · 02-02-2012

You should learn to use a debugger, it's an incredibly useful too. It would have helped you pinpoint the line that causes your seg fault and you could examine the values to see where it went wrong. Have you at least tried printing out the values for value1, high and low at the top of the function? What output does that give you? BTW, you should use stderr for debugging output since stdout is line buffered, so sometimes debugging output doesn't show up right away, leading you to look in the wrong place for the error. Also, I'm not sure you have a valid base case in there.

**deltanosix** · 02-02-2012

Thanks for the suggestion on the new code. When I try to compile it, however, it says error: control reaches end of non-void function

what does this mean?

Thanks again for the help!

**laserlight** · 02-02-2012

It means that you failed to return a value when you were supposed to.

**deltanosix** · 02-02-2012

Aren't I returning true or false? What am I doing wrong?

**laserlight** · 02-02-2012

Originally Posted by deltanosix

Aren't I returning true or false? What am I doing wrong?

What does the function from post #2 return when value1 < array1[middle]?

**deltanosix** · 02-02-2012

Isn't it returning the function sort2? Even when I write return in front of the function, I still have the same problem...not sure what I'm doing incorrect.

**laserlight** · 02-02-2012

Originally Posted by deltanosix

Isn't it returning the function sort2?

Nope. You are just calling the function but not returning a value.

Originally Posted by deltanosix

Even when I write return in front of the function, I still have the same problem.

What does the function from post #2 return when value1 > array1[middle]?

**deltanosix** · 02-02-2012

Well I thought it was returning sort2 again, only with different values. How do I get it to return the function so it will keep looping?

**sparkomemphis** · 02-02-2012

Originally Posted by deltanosix

Aren't I returning true or false? What am I doing wrong?

what do you return for the 3rd (value1 < array1[middle]) and 4th (value1 > array1[middle] cases ?

Also what happens when value1 is not in the array ?

**deltanosix** · 02-02-2012

I thought if the value1 was not in the array, then high == low and it returns false. I also thought that in cases of the value1 < array1[middle], and the opposite, it calls the function again, but updating the values until value1 == middle or high == low.

**iMalc** · 02-02-2012

Perhaps this example will help:

Code:

int factorial(int n)
{
    if (n <= 1)
        return 1;
    else
        return factorial(n-1) * n;
}

**deltanosix** · 02-02-2012

I'm still not sure what I'm doing wrong...

Thread: Recursion problem

Thread Tools

Search Thread

Display