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.

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");
*/

---

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.

Quote:

---

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.