Thread: Function call stack in c - recursion basics related.

Hi ,
Im trying to understand very deeply what's going with stack frame in terms of stack param storing once calling the function , even more complex on recursion case.

As understand once we call a function then stack frame is created and such parameters are stored :

• Return address of caller function - on other words stack pointer of the instruction is where caller function stops on the code line when calling other function.
• Input params.
• Local Variables.

following are some related concerns to what's explained above :

First query #1 :

assume I have only main function then stack frame for it is ofcourse created .. now my concern is what is the return address stored on the stack frame of main() function?

First query #2 :

If I have a recursive function, each call to the function creates a new stack frame. For instance, if I call the function 10 times (f1, f2, ..., f10), the there will be 10 stack frames for same function because its recursive .. and let's assume each function is called at the same line of code marked by a red as you see on the example below, I am concerned about the return address stored on the stack frame of each recursive call since each call stops at the same line of code, I wonder if the return address stored on the stack frame is the same for all the recursive calls?

Code:

int foo(int a)
{
     if (a>1)
        {
            a = foo(a/2);
         }
     return a;
}

Third query #3 :

the return address is actually the register $ra or $esp on assembly language ... Yes?



Thanks much.

Originally Posted by john.c

1. There is a hidden startup function:

Code:

startup:
   ...
   call main
   ...
   exit process ("return" to operating system) with exit system call

2. Yes, of course it's the same.

3. No. What does that even mean?

I understand point 2 (second queston).

regard to first question answer , Yes I understand that there's a __start function which is kind of c library environment and the value of the main is returned to "operating system".

to be honest on concern here when we say returned to "operating system" what do we mean? .. what is concerning me is that the operating system itself also executing the instructions of the code .. so when we say "return to OS" we mean what exactly?


regard to third question, What I mean by third question is actually some reserved registered related to CPU arch (arm or x86 lets say ) which those reserved registered are used for address return normally in assembly ...



thanks much

Originally Posted by Salem

> I wonder if the return address stored on the stack frame is the same for all the recursive calls?
It's the same value, but stored in different places.

You've over-thinking this way too much.

Code:

void baz() {
}
void bar() {
    baz();
}
void foo() {
    bar();
}
int main() {
    foo();
}

I assume you have no trouble comprehending what's going on here.

Recursion is nothing magic, despite it having a special name.

It's just one function calling another function.
The fact that it is itself doesn't change how functions are called and returned from.

totally you convinced me, one point here regard to your statement " stored in different places " .. what do you mean by different places? could you elaborate more ..

Originally Posted by Salem

Each stack frame is like the element of an array.

array[0] is in a different (but nearby) place to array[1]

Calls are like frame[0] frame[1] frame[2]
Returns are like frame[2] frame[1] frame[0]

I got you so I can say it's same address returned because we call the "same function" at "same line of code" and this only leads to that same address is returned , otherwise would be different .. , Yes?

For query 3, different CPUs handle it differently.

Intel x86 CPUs manage the call stack for you, so have a "Stack Pointer" register, and a "Base Pointer" register. When you call a subroutine the CPU will write the return address to the stack.

More RISC-like CPUs usually have all registers as general purpose registers, will have "jump and save" instruction, that jumps to an address, and saves the return address into a nominated register. A subroutine will then save that return address from the general purpose to the stack, and update the general purpose register that is functioning as the stack pointer.

Originally Posted by AkamiKhmenisky

I got you so I can say it's same address returned because we call the "same function" at "same line of code" and this only leads to that same address is returned , otherwise would be different .. , Yes?

No. The return address relates to the calling function, not the called function.

If two different functions both called down to the same lower-level function, they wouldn't put the same address on the stack, because the return address is the location where the program is going to return to. So if a() calls down to z() then when z() tries to return, it needs to return to a(). So the stack will have some address inside a(), like a + 20 bytes, that will be the return address. When b() calls down to z(), again, the call stack will have some address relative to b() stored, because that is where the execution has to go back to.

On the other hand, there is such a thing as a "function pointer". It puts the address of a function inside a variable, and you can call through the variable without knowing what function you are calling.

If you have a single function that calls through a function pointer, you could have two entirely different targets that wind up being called with the exact same return address, because they both got called through the pointer, and so they both need to return to right-after-that in the code.

So:

1. With recursion, the call stack will tend to have the same return addresses, because the "shape" of the recursive function will only provide a couple of possible values (except for the very first call to the recursive function, which was called by some other function).

2. In general, different calling functions will produce different return addresses, because the return address is a location inside the calling function, not the callee function.

3. Using a function pointer would make it possible to call different functions from the same return location.

I don't know what, if any, compiler you have access to. I believe that clang and gcc both provide a builtin function called something like "__builtin_return_address" or something close. That returns a pointer that it gets from the stack, so you could actually call printf() and print out the actual address numbers.

I got it , thank you all.