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.

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.

Certainly looks very heavy on the stack space to me :)

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!!

Instead of trying to increase the stack size, turn the recursion into iteration, using an explicit stack if necessary (it is unnecessary here).

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!

Quote:

---

Originally Posted by esacmils

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

If you really must use "recursion" you could whip up your own stack allocated on the heap and grow as required.

Quote:

---

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

---

not a bad guess at all :D

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.

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

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.

Quote:

---

Originally Posted by c++0x

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

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);
}

---

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. :(

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.

Since stack is a struct stacker object, not a pointer, the -> notation is not correct. The warning about malloc() is because of a missing #include <stdlib.h>.