Like Tree3Likes

Recursion problem

This is a discussion on Recursion problem within the C Programming forums, part of the General Programming Boards category; Hello, I'm running a binary search using recursion, and I keep getting a segmentation fault. Here is the part of ...

  1. #1
    Registered User
    Join Date
    Jan 2012
    Posts
    10

    Recursion problem

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

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    2,768
    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);
        }
    }
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    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.
    stahta01 likes this.

  5. #5
    Registered User
    Join Date
    Jan 2012
    Posts
    10
    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!

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    It means that you failed to return a value when you were supposed to.
    stahta01 likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jan 2012
    Posts
    10
    Aren't I returning true or false? What am I doing wrong?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    Quote 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]?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Jan 2012
    Posts
    10
    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.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,271
    Quote Originally Posted by deltanosix
    Isn't it returning the function sort2?
    Nope. You are just calling the function but not returning a value.

    Quote 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]?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Jan 2012
    Posts
    10
    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?

  12. #12
    Registered User
    Join Date
    Jun 2011
    Posts
    76
    Quote Originally Posted by deltanosix View Post
    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 ?

  13. #13
    Registered User
    Join Date
    Jan 2012
    Posts
    10
    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.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Perhaps this example will help:
    Code:
    int factorial(int n)
    {
        if (n <= 1)
            return 1;
        else
            return factorial(n-1) * n;
    }
    stahta01 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Jan 2012
    Posts
    10
    I'm still not sure what I'm doing wrong...

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with recursion
    By Modest Mouse in forum C Programming
    Replies: 2
    Last Post: 10-10-2011, 11:26 AM
  2. Recursion problem
    By chaklader in forum C Programming
    Replies: 6
    Last Post: 05-28-2010, 10:34 PM
  3. Recursion Problem
    By kuma0177 in forum C Programming
    Replies: 2
    Last Post: 10-15-2009, 11:16 PM
  4. Recursion problem
    By ramayana in forum C Programming
    Replies: 3
    Last Post: 11-13-2006, 11:54 PM
  5. recursion problem
    By dustinc in forum C++ Programming
    Replies: 1
    Last Post: 10-29-2001, 04:29 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21