A Problem with recursion

This is a discussion on A Problem with recursion within the C++ Programming forums, part of the General Programming Boards category; i have to make a program that does quick searching and well it works fine untill someone enters a number ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    40

    A Problem with recursion

    i have to make a program that does quick searching and well it works fine untill someone enters a number not in the list

    here is the function
    Code:
    int q_search(int ray[], int find, int left, int right)
    {
    	int Pivot = (left + right) / 2;
    
    	if(ray[Pivot] > find && Pivot-left != 1)
    		Pivot = q_search(ray, find, left, Pivot);
    	else if(ray[Pivot] < find && right-Pivot != 1)
    		Pivot = q_search(ray, find, Pivot, right);
    	
    	if(ray[Pivot]==find)
    		return Pivot;
    	if(right-Pivot==1 || Pivot-left == 1 && ray[Pivot] != find)
    		return -1;
    }
    thx for any help

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    is it required to use recursion? its probably easier to use iterative method, which also runs faster and uses a lot less memory.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I'm guessing he's required to use recursion.

    Why do you check to see if Pivot-left or right-Pivot are not equal to one? Also, I'm not sure that last if statement will work the way you intend it, order of operations says to evaluate the && first and then the || second.

    Heres a simple example of how this function probably doesn't work: Search for the number 2 in the simple array {0,2}. You'd call q_search(ray, 2, 0, 1). The pivot would be 0, the first if statement fails because ray[0] is less than 2, the second if statement fails because right-Pivot equals 1, the third if statement fails because ray[0] is not equal to 2 and the last if statement is true because right-Pivot equals 1 and (true || false && false)==true. It then returns -1 even though the number 2 is actually in the array.

    The recursive version of the quick find is usually something like this:
    Code:
    int q_search(int ray[], int find, int left, int right)
    {
       return -1 if left>right
    
       if left==right and ray[left] isn't the number you are looking for return -1, if it is return left
    
       pivot=(left+right)/2
    
       if ray[pivot] is the number you're looking for, return pivot
    
       if ray[pivot] is greater than the number, return q_search(ray, find, left, pivot-1)
       else return q_search(ray, find, pivot+1, right)
    
    }
    Last edited by PJYelton; 09-28-2005 at 04:57 PM.

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    224
    the function works just fine until you try to search for a number that isnt in the list... so ill try using parenthesis were the order of opperation is incorrect.

    thx though

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Okay, but trust me, search for the the number 2 in the array (0,2) and you'll get -1

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion problem
    By trnd in forum C Programming
    Replies: 2
    Last Post: 02-01-2009, 03:06 PM
  3. Problem of understanding recursion
    By ixing in forum C Programming
    Replies: 2
    Last Post: 05-02-2004, 04:52 PM
  4. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 09:37 AM
  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