Segmentation fault on recursive function

Hey guys, I am having segmentation fault on recursive function @ int fill_array(). If I enter number like 0 to 16100, the program works fine. For any integer > 16100, the program crashes.

I am running out of ideas what is the problem. Can someone enlighten me?

Code:

---

#include <stdio.h>

int palindrome(int start, int end, int count);
int fill_array(int arr[], int num, int start);
int check_array(int arr[], int num, int end);

int main(void)
{
        int count = 0, start, end;

        printf("Enter start and end: ");
        scanf("%d %d", &start, &end);
       
        count = palindrome(start, end, count);

        printf("Number of palindrome numbers = %d\n", count);

        return 0;
}

int palindrome(int start, int end, int count){
        int array[9], counter;
        if(start > end){
                return count;
        }else{
                counter = fill_array(array, start, 0);
                count += check_array(array, start, counter);
                return palindrome(++start, end, count);
        }
}

int fill_array(int arr[], int num, int start){
        if(num != 0){
                arr[start] = num % 10;
                return fill_array(arr, num/10, ++start);
        }else{
                return start;
        }
}

int check_array(int arr[], int num, int end){
        if(end == 0){
                return 1;
        }else if(num % 10 != arr[end-1]){
                return 0;
        }else{
                return check_array(arr, num/10, --end);
        }
}

---

I try malloc array in palindrome() but it still won't works :(

Those values worked fine for me. There's nothing really wrong with your program. You're probably just blowing out your stack. You call palindrome recursively 16100 times, and eventually you use up all your stack space. That means subsequent function calls use invalid memory and thus your seg fault. Any particular reason you chose to do this recursively? It can be done with a couple simple loops.

You can tried the input of 0 to 654321 :) It will fails.

This is for school work. I am restricted to using recursive. :(

Error as shown in gdb:

Attachment 10985

Well it is a massively recursive solution.

Here's your code with some additional diagnostic.

Code:

---

#include <stdio.h>

int palindrome(int start, int end, int count);
int fill_array(int arr[], int num, int start);
int check_array(int arr[], int num, int end);
int depth;
int maxDepth;

int main(void)
{
    int count = 0, start, end;

    printf("Enter start and end: ");
    scanf("%d %d", &start, &end);

    count = palindrome(start, end, count);

    printf("Number of palindrome numbers = %d\n", count);
    printf("Max recursive depth=%d\n",maxDepth);
    return 0;
}

int palindrome(int start, int end, int count){
    int array[9], counter;
    int result;
    if ( ++depth > maxDepth ) maxDepth = depth;
    if(start > end){
        result = count;
    }else{
        counter = fill_array(array, start, 0);
        count += check_array(array, start, counter);
        result = palindrome(++start, end, count);
    }
    depth--;
    return result;
}

int fill_array(int arr[], int num, int start){
    int result;
    if ( ++depth > maxDepth ) maxDepth = depth;
    if(num != 0){
        arr[start] = num % 10;
        result = fill_array(arr, num/10, ++start);
    }else{
        result = start;
    }
    depth--;
    return result;
}

int check_array(int arr[], int num, int end){
    int result;
    if ( ++depth > maxDepth ) maxDepth = depth;
    if(end == 0){
        result = 1;
    }else if(num % 10 != arr[end-1]){
        result = 0;
    }else{
        result = check_array(arr, num/10, --end);
    }
    depth--;
    return result;
}

---

And my results.

Code:

---

$ ulimit -s
8192
$ ./a.out
Enter start and end: 0 16000
Number of palindrome numbers = 259
Max recursive depth=16007

---

My machine allows 8MB of stack, but on a 1MB stack, 16K recursions allows only about 64 bytes of stack space. With 40 bytes simply for the local variables of palindrome, and the parameters of all the functions, you're pretty close to 64 bytes per stack frame.

Since the values are small, you could just store an array of chars, or even an array of nibbles (with a bit more code effort).

You can reduce the amount of space needed for each stack frame by creating the array of ints in main and passing it to palindrome as a pointer to its first element.

That said, are you sure you are not allowed to use a loop construct at all? It makes sense to test your understanding of recursion for the part where you must determine if a number is a palindrome, but using recursion to loop over the range of numbers is just silly.

Quote:

---

Originally Posted by Salem

Well it is a massively recursive solution.

My machine allows 8MB of stack, but on a 1MB stack, 16K recursions allows only about 64 bytes of stack space. With 40 bytes simply for the local variables of palindrome, and the parameters of all the functions, you're pretty close to 64 bytes per stack frame.

Since the values are small, you could just store an array of chars, or even an array of nibbles (with a bit more code effort).

---

Thanks for the diagnostic!

The stacks is too deep and it is running out of memory. :frown:

Quote:

---

Originally Posted by laserlight

You can reduce the amount of space needed for each stack frame by creating the array of ints in main and passing it to palindrome as a pointer to its first element.

That said, are you sure you are not allowed to use a loop construct at all? It makes sense to test your understanding of recursion for the part where you must determine if a number is a palindrome, but using recursion to loop over the range of numbers is just silly.

---

I already tried malloc-ing the array and free it in palindrome. Still won't works :(

Yeah, I am not allowed to use a loop to construct. The school is damn stupid. There are so many recursion concepts and they choose to select one that require such a big amount of times to "loop" through the stack.

Quote:

---

Originally Posted by xbfish

You can tried the input of 0 to 654321 :) It will fails.

This is for school work. I am restricted to using recursive. :(

---

Does the assignment say you have to be able to handle really large sets of numbers like 0 to 16,000? Tell your professor or TA what is happening and ask if it will be a problem and what you should do about it. Maybe they'll tell you they will only test smaller sets of numbers. Also, perhaps you could do something like:

Code:

---

for (i = start; i < end; i++)
    if (recursive_palindrome_check(i)) {
        palindrome_count++;
    }
}

---

That way, you check individual numbers recursively, but can use a regular loop for iterating over your set of numbers. Checking an individual number shouldn't use up more than a half dozen or so stack frames, so you wont have to worry about crashing.

Quote:

---

Originally Posted by xbfish

I am lazy to use pointer

---

You are already doing that in fill_array anyway. An alternative is to make the array a static local instead. Since you are always calling fill_array on it, you don't need a new array for each recursive call. Of course, this just alleviates the problem of a limited stack; it does not solve it (but then as memory is always bounded, this is true even for the heap).

Quote:

---

Originally Posted by anduril462

Does the assignment say you have to be able to handle really large sets of numbers like 0 to 16,000? Tell your professor or TA what is happening and ask if it will be a problem and what you should do about it. Maybe they'll tell you they will only test smaller sets of numbers. Also, perhaps you could do something like:

Code:

---

for (i = start; i < end; i++)
    if (recursive_palindrome_check(i)) {
        palindrome_count++;
    }
}

---

That way, you check individual numbers recursively, but can use a regular loop for iterating over your set of numbers. Checking an individual number shouldn't use up more than a half dozen or so stack frames, so you wont have to worry about crashing.

---

I will ask them if I am able to use loop for filling array. It makes me look stupid now. LOL!

Quote:

---

Originally Posted by laserlight

You are already doing that in fill_array anyway. An alternative is to make the array a static local instead. Since you are always calling fill_array on it, you don't need a new array for each recursive call. Of course, this just alleviates the problem of a limited stack; it does not solve it (but then as memory is always bounded, this is true even for the heap).

---

I tried malloc an array in palindrome() and then after getting the output I wanted, I free it and recursively call palindrome() again.

Sad to say, it's not working. :frown:

Quote:

---

Originally Posted by xbfish

I will ask them if I am able to use loop for filling array.

---

I find it more likely that you are expected to use a loop construct to loop over the range of numbers than to fill the array since filling the array could be considered part of the steps needed to determine if a number is a palindrome.

Oh, but anduril462's idea that your instructors might not even stress test this much is a good one: consult them.

Quote:

---

Originally Posted by xbfish

I tried malloc an array in palindrome() and then after getting the output I wanted, I free it and recursively call palindrome() again.

---

A static local would be easier.