Where is the overhead in the function call

This is a discussion on Where is the overhead in the function call within the C Programming forums, part of the General Programming Boards category; I have one reverse string that uses iteration: Code: void reverse(char *s) { if(s && *s) { size_t len = ...

  1. #1
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329

    Where is the overhead in the function call

    I have one reverse string that uses iteration:

    Code:
     void reverse(char *s)
     {
       if(s && *s)
       {
         size_t len = strlen(s) - 1;
         char *p = s;
         char *q = p + len;
         char tmp = *p;
         while(p < q)
         {
           *p++ = *q;
           *q-- = tmp;
           tmp = *p;
         }
       }
     
     }
    And one that uses recursion:

    Code:
     
     void recurse(char *p, char *q)
     {
       if(p < q)
       {
         char tmp = *p;
         *p = *q;
         *q = tmp;
         recurse(p + 1, q - 1);
       }
     }
     
     void recerse(char *s)
     {
       if(s && *s)
       {
         size_t len = strlen(s) - 1;
         char *p = s;
         char *q = p + len;
         recurse(p, q);
       }
     
     }
    Now, I call the both the recursive and iterative reverse function a minimum
    of 5 million times. Here is where I get confused. I had someone tell me that
    on the recursive version of the reverse string, I would have a call of of 2.5
    million.

    The question is, is it strlen() or recerse() that would have a call depth of
    2.5 million. Ie, 2.5 million function calls.

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Code:
    #include <stdio.h>
    #include <string.h>
    
    void recurse(char *p, char *q)
     {
    printf("recurse(\"&#37;s\",\"%s\");\n", p, q);
       if(p < q)
       {
         char tmp = *p;
         *p = *q;
         *q = tmp;
         recurse(p + 1, q - 1);
       }
     }
    
    void recerse(char *s)
     {
    printf("recerse(\"%s\");\n", s);
       if(s && *s)
       {
         size_t len = strlen(s) - 1;
    printf("strlen(\"%s\");\n", s);
         char *p = s;
         char *q = p + len;
         recurse(p, q);
       }
     
     }
    
    int main( void )
    {     
       char text[] = "Hello world";
       recerse(text);
        return 0;
    }
    
    /* my output
    recerse("Hello world");
    strlen("Hello world");
    recurse("Hello world","d");
    recurse("ello worlH","lH");
    recurse("llo woreH","reH");
    recurse("lo woleH","oleH");
    recurse("o wlleH","wlleH");
    recurse(" olleH"," olleH");
    */
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329
    I see.

  4. #4
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329
    Now, here is the other question. I was told using calling reverse string recursively was bad because of apparent function call overhead. However, I see that the overhead is in the recursive function itself and not in strlen(). How much different is this than using recursion in a binary tree?

    I mean, if I have a binary tree, I would still be getting repated calls to recurse(). The only thing I can possibly think of is that recursive call to reverse string runs in linear time, whereas a recursive call in a binary tree can run in logarithmic time.

  5. #5
    Registered User
    Join Date
    Feb 2006
    Posts
    54
    Quote Originally Posted by Overworked_PhD View Post
    Now, here is the other question. I was told using calling reverse string recursively was bad because of apparent function call overhead. However, I see that the overhead is in the recursive function itself and not in strlen(). How much different is this than using recursion in a binary tree?

    I mean, if I have a binary tree, I would still be getting repated calls to recurse(). The only thing I can possibly think of is that recursive call to reverse string runs in linear time, whereas a recursive call in a binary tree can run in logarithmic time.
    In both cases there are some stack operations relating to the function call, that run each time the recursive version calls itself. In a binary tree, a recursive version of some operation might be more efficient in terms of code size, but i doubt it would be faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 04:06 PM
  2. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 07:54 PM
  3. Loading files with a function call
    By ulillillia in forum C Programming
    Replies: 6
    Last Post: 04-10-2007, 08:19 PM
  4. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  5. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM

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