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

  1. #1
    Registered User
    Join Date
    Jan 2024
    Posts
    25

    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.

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,628
    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?
    A little inaccuracy saves tons of explanation. - H.H. Munro

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,659
    > 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.
    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
    Jan 2024
    Posts
    25
    Quote Originally Posted by john.c View Post
    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

  5. #5
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by Salem View Post
    > 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 ..

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,659
    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]
    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.

  7. #7
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by Salem View Post
    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]
    Got you totally , you meant different places in terms of stack frames positions.

    second concern , the code itself is executed by CPU and not by operating system , so when we say main function return 0 to OS, we mean what exactly? OS waiting for that main() returned value implicitly?
    what is confusing me is that what I know that CPU is executing the program instruction and not OS .. so where OS comes into picture? .. can we say CPU is actually OS? if you can clear this gap please.
    Last edited by AkamiKhmenisky; 01-29-2024 at 03:28 PM.

  8. #8
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    Quote Originally Posted by Salem View Post
    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?

  9. #9
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    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.

  10. #10
    Registered User
    Join Date
    Apr 2021
    Posts
    139
    Quote Originally Posted by AkamiKhmenisky View Post
    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.

  11. #11
    Registered User
    Join Date
    Jan 2024
    Posts
    25
    I got it , thank you all.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function call Overhead and Function Call Stack
    By Alam Khan in forum C++ Programming
    Replies: 2
    Last Post: 04-26-2014, 08:28 AM
  2. Stack overflow in recursion
    By Nom1fan in forum C Programming
    Replies: 4
    Last Post: 11-24-2010, 12:51 PM
  3. how to get function call stack
    By George2 in forum C Programming
    Replies: 18
    Last Post: 11-11-2006, 07:51 AM
  4. Help Related Linked Lists Basics
    By ketav in forum C++ Programming
    Replies: 5
    Last Post: 11-11-2006, 01:53 AM
  5. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM

Tags for this Thread