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

I see.

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.

Originally Posted by Overworked_PhD

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.