Chad said:
Don't we also increase the stack depth on a Binary Search Tree
everytime we add a node to the tree?
Yes, but.
If I remember correctly, we use
recursion to add a node to a Binary Search Tree.
Yes, but.
How would this be much
more different than using a recursive version of reversing a string in
place?
If you naively add nodes to a binary search tree without taking due account
of the "shape" of that tree, and if you use recursion to add or search for
nodes (which is not a given - IIRC Ben Pfaff's libavl does not use
recursion), then you do run the risk of exceeding the machine's ability to
cope with that kind of call depth. But of course you can be mildly clever,
and balance the tree as you go. Also, if you do choose to use recursion,
you gain in expressive power - it's easy to write a set of recursive
functions to handle a binary tree, but rather harder to write an iterative
set.
Here's a string reversing routine that uses iteration:
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;
}
}
}
Here's a version that uses recursion:
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);
}
}
As you can see, I've wrapped the recursive function inside another function
that calculates the length of the string. I'm sure it's possible to avoid
calling strlen over and over again without writing a wrapper, but this was
the quickest, most obvious way I could find. As you can see, the recursive
version is slightly longer and rather less obvious than the iterative
version. And if the string is, say, a description of a DNA strand 5,000,000
bases long, then you're looking at a call depth of 2.5 million - whereas
the iterative version will have a call depth of just 1. And it won't need
the overhead of 2.5 million function calls, either.
}