# Thread: Where is the overhead in the function call

1. ## 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. 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");
*/```

3. I see.

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

Popular pages Recent additions