Thread: Segmentation fault on recursive function

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    10

    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
    Last edited by xbfish; 10-12-2011 at 09:47 AM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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.

  3. #3
    Registered User
    Join Date
    Jul 2011
    Posts
    10
    You can tried the input of 0 to 654321 It will fails.

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

  4. #4
    Registered User
    Join Date
    Jul 2011
    Posts
    10
    Error as shown in gdb:

    Segmentation fault on recursive function-2ccqu5e-jpg

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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 Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jul 2011
    Posts
    10
    Quote Originally Posted by Salem View Post
    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.

  8. #8
    Registered User
    Join Date
    Jul 2011
    Posts
    10
    Quote Originally Posted by laserlight View Post
    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.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by xbfish View Post
    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.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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 Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Jul 2011
    Posts
    10
    Quote Originally Posted by anduril462 View Post
    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!

  12. #12
    Registered User
    Join Date
    Jul 2011
    Posts
    10
    Quote Originally Posted by laserlight View Post
    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.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function and segmentation fault
    By davidjg in forum C Programming
    Replies: 4
    Last Post: 02-11-2011, 10:23 AM
  2. Segmentation fault: vector to function
    By ArlexBee-871RBO in forum C++ Programming
    Replies: 1
    Last Post: 09-28-2008, 04:36 AM
  3. A libdc1394 library function is causing a segmentation fault
    By Phanixis in forum Linux Programming
    Replies: 7
    Last Post: 10-16-2007, 12:44 PM
  4. Replies: 2
    Last Post: 10-29-2005, 06:05 PM