Run-time execution for recursive functions.

This is a discussion on Run-time execution for recursive functions. within the C Programming forums, part of the General Programming Boards category; Hi, I actually dont know how CPU (or the compiled run-time code) handles recursive functions. Is the code of the ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    145

    Run-time execution for recursive functions.

    Hi,
    I actually dont know how CPU (or the compiled run-time code) handles recursive functions. Is the code of the function copied “a-la memcpy” to make a new instance? Or only the local vars are copied for the new instance?
    Does the size of the function influence on the speed of the recursive function? If so, are long-inline macros be counter-productive, and better to have as normal function calls?
    I ask all this because I don’t know exactly how run-time execution handles subroutines (above all in recursive funcs.).
    Thanks.

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    The code isn't "copied" at all, there is only one instance of it in memory, the program counter just moves around. Each call to the function results in new instances of the local variables (local to that specific instance of the function [unless they are static]) pushed onto the stack. As far as the code itself goes, each time the function is called again, the program counter gets reset to point to the beginning of the function's code (the address of instruction we made the recursive call from is saved to jump back to after the current instance of the function ends). When the function ends, the current instances' local variables are popped off the stack and the program counter gets set back to the last saved value so we can pick up where we last let off.

    ... at least that's how I imagine it happens in my head.
    Last edited by hk_mp5kpdw; 03-25-2009 at 11:28 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Which is why you can overflow the stack with recursion that goes too deep (push, push, push, push....).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    The main point being the compiler does absolutely nothing special to make a recursive call. It is exactly like any other call.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Registered User
    Join Date
    Feb 2008
    Posts
    145
    Quote Originally Posted by hk_mp5kpdw View Post
    The code isn't "copied" at all, there is only one instance of it in memory, the program counter just moves around. Each call to the function results in new instances of the local variables (local to that specific instance of the function [unless they are static]) pushed onto the stack. As far as the code itself goes, each time the function is called again, the program counter gets reset to point to the beginning of the function's code (the address of instruction we made the recursive call from is saved to jump back to after the current instance of the function ends). When the function ends, the current instances' local variables are popped off the stack and the program counter gets set back to the last saved value so we can pick up where we last let off.

    ... at least that's how I imagine it happens in my head.
    I see, so as more local vars means more stack load to work with.
    Does non-recursive function copy its local vars also in stack?

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Quote Originally Posted by Kempelen View Post
    I see, so as more local vars means more stack load to work with.
    Does non-recursive function copy its local vars also in stack?
    function does not know if it recursive or not.
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Local vars are on the stack, yes.

  8. #8
    Registered User
    Join Date
    Feb 2008
    Posts
    145
    Quote Originally Posted by nonoob View Post
    Local vars are on the stack, yes.
    So the bigger the function and the more local vars you use, the bigger the work load of the stack. For speed purposes (and also for methodology) it is better to have a few small function that one that do all.no?

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Using one large funciton or several small ones is a compromise. If all functions are one long chain of calls (func1 calls func2 that calls func3), then the stack overhead is (a tiny bit) larger than if you put all the code for func1..func3 in one function - because each function call itself must also use some stack-space to store where to return to.

    The general rules are:
    1. Keep functions reasonably small - it makes them possible to read, and the compiler often optimizes small functions better than large ones.
    2. A function should do one thing, and do it well.
    3. If something is repeated several times in the code, make it a function.

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. execution time
    By shuo in forum C++ Programming
    Replies: 3
    Last Post: 10-17-2007, 02:58 AM
  2. having a real tough time with functions..
    By simstim99 in forum C++ Programming
    Replies: 6
    Last Post: 04-30-2007, 12:48 AM
  3. execution time in C , Linux
    By vinayonnet in forum C Programming
    Replies: 4
    Last Post: 06-21-2006, 01:06 PM
  4. What is the best way to record a process execution time?
    By hanash in forum Linux Programming
    Replies: 7
    Last Post: 03-15-2006, 06:17 AM
  5. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 09:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21