Recursion in C and the Stack

[spix]

Hi

In my programs, when I want to perform an operation on a directory recursivley, I use a recursive function.

Am I right in thinking that the stack is used for the local variables of the parent function?

I am worrying that if I have a large variable, say 1024 bytes in size, and my operating system provides stacks that are 4096 bytes in size, after at most 4 recursions my stack is going to overflow.

I don't seem to be seeing this behaviour, is it just luck? Or have I missunderstood something and have no need to worry?

Thanks
Andrew

[Midas]

Your thinking is right: the local variables to a function are declared in the stack. A recursive call causes the creation of a new stack frame for this called function 'instance' - the local variables for this new function 'instance' will again be stored here.

So, as you say, you will overflow the stack after 4 recursions. One possible reason that you aren't seeing this behaviour, however, is that a very common type of recursion - tail recursion - is easily optimised to an iterative (loop-based) approach.

[spix]

Your thinking is right: the local variables to a function are declared in the stack. A recursive call causes the creation of a new stack frame for this called function 'instance' - the local variables for this new function 'instance' will again be stored here.

How does this fit in with the BSS? The other thing I had thought might happen is the BSS stores the data but the stack stores a pointer to the data, but in this case I should be overwriting the data at every recursion?

the actual variable is a:

char buffer[1024]

[Midas]

NOTE: The following was posted earlier, but I deleted and reposted as I made a change.


The BSS segment is used to store global variables. The local variable will be defined on the stack, unless it's declared as static - in which case I'm not certain what happens, but I think it may still get placed in the BSS (the difference then being that the local variable is still scoped differently than the global variable).

EDIT: Addition follows:

With your example, you'd be likely to get the following (remembering that stack grows downwards, normally):

Initial call ('first function'):

Code: Select all

EBP: Points to start of stack frame for this function.
ESP: Points to [EBP - 1024].
Stack:
    Any arguments to your function
    Return address
Start of stack frame - where EBP points to
    1024 bytes of your variable
End of stack frame - where ESP points to

1st recursion ('second function'):

Code: Select all

EBP: Points to start of stack frame for this recursed instance of the function
ESP: Points to [EBP - 1024]
Stack:
    Any arguments to the initially called function
    Return address
Start of first function's stack frame
    1024 bytes of its variable
End of first function's stack frame
        Any arguments to this recursed instance of the function
        Return address for previous instance of function
    Start of second function's stack frame
        1024 bytes of second function's variable
    End of second function's stack frame

2nd recursion ('third function'):

Code: Select all

EBP: Points to start of stack frame for this recursed instance of the function
ESP: Points to [EBP - 1024]
Stack:
    Any arguments to the initially called function
    Return address
Start of first function's stack frame
    1024 bytes of its variable
End of first function's stack frame
        Any arguments to this recursed instance of the function
        Return address for previous instance of function
    Start of second function's stack frame
        1024 bytes of second function's variable
    End of second function's stack frame
            Any arguments to this recursed instance of the function
            Return address for previous instance of function
        Start of third function's stack frame
            1024 bytes of third function's variable
        End of third function's stack frame

And so on. So your example, assuming no arguments, might look like the following when it overflows the stack:

Code: Select all

EBP: Points to start of stack frame for this recursed instance of the function  (3rd recursion - 4th instance)
ESP: Points to [EBP - 1024]
Stack:
    Return address
Start of first function's stack frame
    1024 bytes of one instance of buffer
End of first function's stack frame
        Return address
    Start of second function's stack frame
        1024 bytes of another instance of buffer
    End of second function's stack frame
            Return address
        Start of third function's stack frame
            1024 bytes of another instance of buffer
        End of third function's stack frame
                Return address
            Start of fourth function's stack frame
                1024 bytes of another instance of buffer
            End of fourth function's stack frame
End of your designated stack here
                    Return address - already overflowed
                Start of fifth (first overflowed) function's stack frame
                    1024 bytes of another instance of buffer
                End of fifth function's stack frame

It should be noted that 'instance' when referring to instances of the function (not of buffer - there are multiple copies of a variable which might be called 'buffer' in memory) is being used loosely - and temporally - rather than to refer to separate instances of the function in memory. There is only one copy, which is executed multiple nested times.

[ces_mohab]

I am worrying that if I have a large variable, say 1024 bytes in size, and my operating system provides stacks that are 4096 bytes in size, after at most 4 recursions my stack is going to overflow.

you mustn't use large local variables in a recursive function.

I think copying a directory first make a tree of directory structures and then loop through this tree to copy all files. or even make recursion in this tree. but making large local variables in a recursive function is a bad idea.

an idea to allocate 1024 data is to use only pointer local variable then allocae memory for this variable. after recursion free this variable.

[spix]

Ok thanks for all the help..

I've kept the recursion, but changed it so I only have little variables. That will do for now until I make a better non recursive thing.

[B.E]

There is another way you can "emulate" recursion. You can create your own stack structure on the heap.