Difficulty with understanding recursion and pointers

**mdt0322** · 08-01-2013

I am taking a class on C programming and am struggling to understand recursion and pointers. I did poorly on an assignment on these and would appreciate it if anyone could help explain this program to me.

What I'm looking to get help on is how the recursive step leads from the start to the base case in binarySearchRecursive, and how you know this progrma ends. The other part I need help with is how the pointers and recursion of the call ptr = binarySearchRecursive(value, &list[0], &list[19]) are used to search through the list given.

Code:

#include<stdio.h>
#include<stdlib.h>

int * binarySearchRecursive(int value, int *first, int *last) {
    int middle;
    
    if(first <= last) {
        middle = (last - first) / 2;
        
        if (*(first + middle) == value) {
            return (first + middle);
        }
        else {
            // move left
            if (*(first + middle) == value) {
                return (first + middle);
            }
            else {    // move right
                return binarySearchRecursive(value, (first + (middle+1)), last);
            }
        }
    }
    else {
        return NULL; // element not found
    }
}

int main() {
    int list[20] = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50,
                        55, 60, 65, 70, 75, 80, 85, 90, 95, 100};
    int *ptr, value = 85;
    
    ptr = binarySearchRecursive(value, &list[0], &list[19]);
    
    if (ptr != NULL) {
        printf("The value %d is at address %p in the sorted array.\n", value, ptr);
        printf("Test:  list[%d] = %d\n\n", (ptr-list), *ptr);
    }
    else {
        printf("%d was not found in the list.\n\n", value);
    }
}

**rcgldr** · 08-01-2013

The code doesn't appear to be correct. The "move left" part is an issue.

**anduril462** · 08-01-2013

First:

Code:

        else {
            // move left
            if (*(first + middle) == value) {
                return (first + middle);
            }

That does not "move left", it checks whether the middle element is the value you're searching for. But it can't be, because you alread checked that on line 10, and you're in the else (i.e. "not the value I'm looking for") clause. You need to compare value to the middle element, and make a recursive call similar to the one on line 19 (but examining elements left of the middle element).

Doing this with pointers instead of indexes is just confusing, and certainly doesn't help you understand the recursive side of it. It would be easier to understand if you used indexes, even though there is a 1:1 correspondence between the two.

That being said, basically you are halving the search space each time. This only works because the list is ordered (a pre-requisite for binary search). Basically, you take the middle element of the list, and compare it to the value. If the value is equal to it, you found it and return. If it's less than that, you look at all the elements less than the middle element (i.e. first up to (first + middle - 1)). If it's greater, you look at (first + middle + 1) up to last. It might help if you print the parts of the list you're examining each time in binarySearchRecursive. Add this function, and call it on line 9:

Code:

void printList(int *first, int *last)
{
  while (first <= last) {
    printf("%d ", *first);
    first++;
  }
  putchar('\n');
}


int * binarySearchRecursive(int value, int *first, int *last) {
  int middle;


  if(first <= last) {
    middle = (last - first) / 2;
    printf("Examining the following list with middle element %d: ", *(first + middle));
    printList(first, last);

**rcgldr** · 08-01-2013

Here is a cleaned up version of the original example:

Code:

#include<stdio.h>
#include<stdlib.h>

int * binarySearchRecursive(int value, int *first, int *last) {
    int middle;
    
    if(first <= last) {
        middle = (last - first) / 2;
        // (note, if first == last, then middle == 0)
        if (*(first + middle) == value) // if match found return it
            return (first + middle);
                
        if (*(first + middle) > value)  // if greater search left half
            return binarySearchRecursive(value, first, first + middle - 1);
                                        // else search right half
        return binarySearchRecursive(value, first + middle + 1, last);
    }
    else                // if first > last, element not found
        return NULL;
}

int main() {
    int list[20] = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50,
                        55, 60, 65, 70, 75, 80, 85, 90, 95, 100};
    int *ptr, value = 85;
    
    ptr = binarySearchRecursive(value, &list[0], &list[19]);
    
    if (ptr != NULL) {
        printf("The value %d is at address %p in the sorted array.\n", value, ptr);
        printf("Test:  list[%d] = %d\n\n", (ptr-list), *ptr);
    }
    else {
        printf("%d was not found in the list.\n\n", value);
    }

    return(0);
}

Thread: Difficulty with understanding recursion and pointers

Thread Tools

Search Thread

Display

Difficulty with understanding recursion and pointers

Similar Threads

Having difficulty understanding strtok()

Understanding recursion by parts difficulty

Understanding recursion - Pls help

Understanding recursion

Problem of understanding recursion