Concatenate null-terminated strings recursively

Question

I'm inventing interview questions that require analysis of C++ code that does something simple with pointers and recursion. I tried to write strcat() in recursive manner:

size_t mystrlen( const char* str )
{
    if( *str == 0 ) {
        return 0;
    }
    return 1 + mystrlen( str + 1 );
}

void mystrcpy( char* to, const char* from )
{
    if( ( *to = *from ) == 0 ) {
        return;
    }
    mystrcpy( to + 1, from + 1 );
}

void mystrcat( char* to, const char* from )
{
    mystrcpy( to + mystrlen( to ), from );
}

What I don't like here is that I have three functions and my strcat() is not very recursive - it just calls two other functions once. Is there a way to rewrite that somehow to reduce the number of functions increasing use of recursion but without sacrificing much of code brevity?

Answer 1

How about:

void mystrcat( char* to, const char* from )
{
    if (*to == '\0')
        mystrcpy( to, from );
    else
        mystrcat( to + 1, from );     
 }

Answer 2

I think you're done. You have two lovely recursive functions, and a one-line call to them.

I can only think of a hackish way to even do it in one function:

void
mystrcat(char* to, const char* from, bool copy_now)
{
    if (!copy_now && *to)
    {
        mystrcat(to+1, from, false);
        return;
    }

    *to = *from;
    if (*to)
        mystrcat(to+1, from+1, true);
}

That almost doesn't suck if you are using C++ and you make copy_now an optional parameter with a default value of false. Then the caller can pretend it doesn't have that extra bit of state.

But if the problem is hard enough to make you ask for help on StackOverflow, it's too hard to be a reasonable interview question. You could ask it just to try to make the person think out of the box, but don't make failure to get a good answer an automatic flunk.

I suggest adding another lovely recursive problem: find the depth of a binary tree.

Given the following struct:

typedef struct s_node
{
    struct s_node *pLeft;
    struct s_node *pRight;
} NODE;

write a function

int tree_depth(NODE *pNode)

that returns the maximum depth of the tree. I was actually asked that question in an interview once and I think it is just the right level of difficulty for an interview. The people you don't want to hire will have trouble with it, and the people you might want to hire will probably enjoy it.

EDIT: I tested the function and found it had a bug. This version has the bug fixed.

Answer 3

In a single function you could write:

// pre: to is a string that is zero-initiallized (all chars are '\0')
void mystrcat( char* to, const char* from )
{
   if ( *to ) mystrcat( to+1, from );
   else {
      if (*to = *from) mystrcat( to+1, from+1 );
   }
}

Note that it is intentionally ugly, it serves to purposes in two branches, it advances the to pointer in the first branch and it copies values in the other. The if condition is intentionally ugly also as most usually you will flag a single = within a condition as a typo, but insist in that it is up, running and tested so that they must work the meaning out themselves.

One other thing you might consider is adding a return statement like:

char* mystrcat2( char* to, const char* from )
{
   if ( *to ) return mystrcat2( to+1, from );
   else {
      if ( *to = *from ) return mystrcat2( to+1, from+1 );
      else return to;
   }
}

Now the interviewed has the second task of interpreting the result of the function when called on two strings, and you can discuss how the efficiency of this strcat version compares to the original both in terms of single string concatenations as well as multiple concatenations (take a look at this article by Joel Spolsky that among other things talks about the Scheimel paint algorithm). You can ask for the implementation of this function in terms of both the strcat and mystrcat:

// concatenates a set of strings into a buffer
//
// pre:  to has memory enough to hold all the contents
//       from[i] is a valid C string for all i smaller than n
void mymultiplecat( char* to, const char* from[], int n )
{
   for ( int i = 0; i < n; ++i ) {
      to = mystrcat( to, from[i] );
   }
}

Answer 4

Well, I don't really see the point in trying to make strcat() "as recursive as possible", even though its just for an interview question. strcpy() is just a strlen() + strcat() and the implementation should reflect that. If a candidate gave the solution you have sketched I would be more than happy - he/she showed that he/she understands 1. recursion and 2. using subroutines to implement more complex functionality.

Answer 5

here's my example (the advantage is it has only one recursive call):

char * mystrcat(char *dest, const char *src){
    if(*dest == 0){
        if(*src == 0)   // end of recursion cond
            return dest;
        *dest = *src++; // actual copy
        dest[1]=0;      // zero out dest buf
    }
    mystrcat(dest+1,src); // advance one char
    return dest;
}

here's rough test code:

main(){
  char c[]={'a',0,'b','c',0};
  //char c[]={0,'b','c',0};
  mystrcat(c,"xy");
  //mystrcat(c,"");
  puts(c);
}

Answer 6

I thought of another answer!

void
mystrcat(char* to, const char* from)
{
    if (*to)
    {
        // keep looking for end of to
        mystrcat(to+1, from);
        return;
    }

    if (*from)
    {
        // make sure we get past first if
        to[1] = '\0';
        // call recursively until end of from found
        mystrcat(to+1, from+1);
        // after call, copy chars on way out
        *to = *from;
    }
}

No extra argument to hold state, and it is still O(n).

I'm not sure I could have come up with this while under the pressure of a job interview, though.

Answer 7

I had an interview question once where I had to write a simple, recursive BSP tree traversal that was an actual, blanked-out function from a full program.

I'd suggest that something like that would be a better way to gauge someone's grasp on recursion than inventing a problem that's not idiomatically solved with recursion in C++. Plus it's exciting for entry level applicants when you run the program and they observe their code working flawlessly.

If you insist on going with strcat, I think it could be more interesting if the task was to recursively concatenate an arbitrary number of strings taken from a linked list. Even if the data copy and string length operations aren't recursive, the traversal of the linked list could be, and I think it would be more interesting as you could actually do work on both the way down and on the way back up.

Answer 8

You want recursion and brevity? Here's something that I think has both qualities without going too far into the code golf weeds (that's not to say it's not ugly - it is):

char* myStrcat( char* to, char const* from)
{
    if (!*from) return to;

    if (!*to) *to++ = *from++, *to-- = '\0';

    return myStrcat( to+1, from) - 1;
}

Note that this version has the added complexity of returning the destination pointer (as in the standard strcat()).

Here's a slightly more readable version that uses a little less 'pseudo-cleverness' like comma operators and decrementing after incrementing to restore the to pointer (steveha's comment prompted me to do this for some reason). On second look at the various answers here is pretty much equivalent to catwalk's answer:

char* myStrcat( char* to, char const* from)
{
    if (!*from) return to;  // terminal condition, no more chars to concatenate

    if (!*to) {
        // since we're at the end of the 'to' string, 
        //    append char from 'from'
        //    and 'consume' it from `from`
        *to = *from++;
        *(to+1) = '\0';
    }

    return myStrcat( to+1, from) - 1;
}

However, please don't associate my name with any of this code (I claim to have stolen it from someone else).