Thread: beginner question recursive functions c memory problem ?

  1. #1
    Registered User
    Join Date
    Dec 2008
    Posts
    4

    beginner question recursive functions c memory problem ?

    i`m trying to code some recursive algorithm and run into a segmentation fault upon executing the program. since i`m quite new to programming, especially in c, i wrote the following piece of code just to find out how far i can go with, what looks to me, the simplest recursive function there is.

    Code:
    #include <stdio.h>
    
    
    void x(long a) // the recursive function which calls itself in order to increase a by one 
    {
    	if(a<1000000){
    	a=a+1;
    	printf("%.5d\n", a);
    	x(a);
    	}
    	else
    		return;	
    	}
    	
    
    
    int main()
    {
    	
    	long b=1;
    	x(b);
     return 0;
    }
    the thing is that on my machine i get to 523797 after which the segmentation fault appears and i would have thought that it should go much farther than that.

    Could anyone explain to me why the segmentation fault appears (i guess its a memory thing) cos i don`t really see why it occurs at such an early stage.

    thx a million in advance.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The people who actually know what's going on will probably correct me, but here goes: each time you call x, you add a return pointer and a new copy of a on to the frame stack. So that's what, eight bytes? Looks like your stack can hold 4MB, which is about four times as large as I would have expected it to be.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Certainly looks very heavy on the stack space to me
    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.

  4. #4
    Registered User
    Join Date
    Dec 2008
    Posts
    4

    i c

    so, is there a way to enlarge the stack size?
    and if yes, what kind of negative impact on the system or the program itself could it have?

    thanks!!

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Instead of trying to increase the stack size, turn the recursion into iteration, using an explicit stack if necessary (it is unnecessary here).
    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

  6. #6
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Anyway, it will use a hell of a lot of stack space.

    Assuming each at each call (being very minimalistic) :-
    * The return address is pushed onto the stack = 4b
    * The frame pointer is pushed onto the stack = 4b * (Probably optimized out)
    * 'a' is pushed onto the stack = 4b
    * Even more if it's not optimized in any way

    At 12b a call. And a stack of 4 * 1024kb (4mb)
    = (4 * (1024^2)) / 12
    ~ 349 525 calls

    Or assuming only 8b per call, and a stack size of 4mb
    = (4 * (1024^2)) / 8
    ~ 524 288 calls (minus other stuff on the stack)
    Not a bad guess!

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by esacmils View Post
    so, is there a way to enlarge the stack size?
    and if yes, what kind of negative impact on the system or the program itself could it have?

    thanks!!
    Increasing stack size is OS dependent. The negative impact of recursion is that it is prone to stack overflow by pushing too many function frames onto the stack. Perhaps use a different routine or algorithm to learn about recursion if you must. Here's a good one from the FAQ.
    http://faq.cprogramming.com/cgi-bin/...&id=1073086407

  8. #8
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    If you really must use "recursion" you could whip up your own stack allocated on the heap and grow as required.

  9. #9
    Registered User
    Join Date
    Dec 2008
    Posts
    4

    ~ 524 288 calls (minus other stuff on the stack)
    Not a bad guess!
    not a bad guess at all

    the algorithm i`m implementing at the moment won`t call itself anywhere near as much as the test program above, but since i didnt know anything about stacks and the like (obviously not a computer science major) i was a bit surprise about the segmentation fault in such a simple program.

    so thanks everyone, that was very helpful.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It's perfectly possible to create a segmentation fault with very simple programs. Seg fault is simply the computers way of telling you that you've tried to do something you shouldn't - like write to memory you don't own, for example.

    I agree, recursion is probably a bad way to solve a problem unless you know for sure that there is enough stack [and bear in mind that changes to your code can cause the amount of stack-space to be reduced].

    The stack has a limit - it may be 4MB, it may be 1MB or even a few KB in some cases (embedded OS's may even have stack of, say, 256 bytes).

    The stack is the bit of memory that holds:
    1. Return address to get back to the calling function.
    2. Local variables.
    3. Parameters to the functions being called.

    So if your recursive function uses large amounts of stack (more/larger local variables, higher number of parameters, etc), you don't get as many recursive calls as your simple code that uses a fairly small amount of stack.

    There are ways to resolve this:
    1. As suggested, implement your own stack using dynamic memory allocation (malloc/free) and instead of recursing, just push the current data onto the stack, and pop off the stack to restore the old values.
    2. Use dynamic memory to store local data - a pointer takes 4 or 8 bytes of space, whilst a data structure may take MANY bytes.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Banned
    Join Date
    Dec 2008
    Location
    Maputo, Mozambique
    Posts
    82
    Interestingly, some optimizers will change your code in a way that eliminates recursion when set to a high enough level. When possible, of course. What you could do is try compiling it with a higher degree of optimization enabled. More importantly I would simply you could just recognize that the recursion you are using in this particular function is entirely unnecessary. You have turned a for loop into something recursive. So simply do not do that.

    Also, you could make your own custom heap to accomplish the same task. Either way would work sufficiently.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by c++0x View Post
    Interestingly, some optimizers will change your code in a way that eliminates recursion when set to a high enough level. When possible, of course. What you could do is try compiling it with a higher degree of optimization enabled. More importantly I would simply you could just recognize that the recursion you are using in this particular function is entirely unnecessary. You have turned a for loop into something recursive. So simply do not do that.

    Also, you could make your own custom heap to accomplish the same task. Either way would work sufficiently.
    First of all, that only works on simple tail recursion (that is, you only call the new function as the last thing), and if you rely on it for your code to function correctly, you may find that you make a small change to the code, and the compiler doesn't recognise that it can iterate instead of recurse, which means that the code suddenly breaks unexpectedly. Not a reliable thing to use.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Banned
    Join Date
    Dec 2008
    Location
    Maputo, Mozambique
    Posts
    82
    Code:
    struct stacker {
      long a
      struct stacker *p;
    } stack = {0,0};
    
    void push(long a)
    {
      struct stacker **p;
      for(p = &stack->p; *p; *p = (*p)->p) ;
      *p = malloc(sizeof(**p));
      (*p)->a = a;
      (*p)->p = 0;
    }
    
    long pop(void)
    {
      struct stacker **p, *b;
      long a;
      for(a = -1, p = &stack->p, b = 0; (*p)->p; *p = (*p)->p) b = *p;
      a = (*p)->a;
      if(b) b->p = 0;
      free(*p);
      return a;
    }
    
    void x(long a)
    {
      do
      {
        if(a<0xF4240)
        {
          printf("&#37;.5d\n", ++a);
          push(a);
        } else return;
      } while((a = pop()) != -1);
    }

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In a recursive program, you might recurse down millions of time, but your program will also be popping back up on the stack, a great deal.

    In a chess program, for instance, you might recursively go down and pop back up, millions of time as the various board positions are considered, but your program will probably go no deeper than 40 or 50 ply (single levels), deep, ever.

    The biggest contribution of recursion is in the elegance of the code, imo. I've seen an iterative (non recursive) version of quicksort, and I'll tell you, it is mighty *ugly*, indeed.

    Towers of Hanoi is another beautiful recursive program. Take out the recursion, and it's now a pretty awful mess.

  15. #15
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    i tried to compile the code c++0x was proposing, and, apart from the missing semicolon after long a, i got the following error messages:

    Code:
    : In function 'push':
    :11: error: invalid type argument of '->'
    :12: warning: incompatible implicit declaration of built-in function 'malloc'
    :In function 'pop':
    :21: error: invalid type argument of '->'
    anyone know why?

    thx very much.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. To find the memory leaks without using any tools
    By asadullah in forum C Programming
    Replies: 2
    Last Post: 05-12-2008, 07:54 AM
  2. Suggestions on this C style code
    By Joelito in forum C Programming
    Replies: 11
    Last Post: 06-07-2007, 03:22 AM
  3. Question regarding recursive functions
    By knj316 in forum C++ Programming
    Replies: 7
    Last Post: 10-01-2006, 11:41 PM
  4. understanding recursive functions
    By houler in forum C Programming
    Replies: 7
    Last Post: 12-09-2004, 12:56 PM
  5. Pointer's
    By xlordt in forum C Programming
    Replies: 13
    Last Post: 10-14-2003, 02:15 PM