# Thread: Difficulty with understanding recursion and pointers

1. ## Difficulty with understanding recursion and pointers

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

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 {
}
}```

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

3. 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);```

4. 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);
}
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 {