Recursion with C

Question

I have the code below to reverse a string recursively, it works when I print the chars after the recursion is finished, but I can not figure out how to assemble the reverse chars into a string and return them reversed to the caller. Anyone have an idea? I don't want to add another parameter to accumulate chars, just this way, this is not homework, I am brushing up on small things since I will be graduating in a year and need to do well on interviews.

char* reversestring5(char* s)
{

    int i = 0;
    //Not at null terminator
    if(*s!=0)
    {

        //advance the pointer
        reversestring5(s+1);
        printf("%c\n",*s);
    }

}

Answer 1

Here's a "there and back again" [Note 1] in-place reverse which:

• doesn't use strlen() and doesn't need to know how long the string is in advance; and

• has a maximum recursion depth of half of the string length.

It also never backs up an iterator, so if it were written in C++, it could use a forward iterator. However, that feature is less interesting because it keeps iterators on the stack and requires that you can consistently iterate forward from an iterator, so it can't use input iterators. Still, it does mean that it can be used to in-place reverse values in a singly-linked list, which is possibly slightly interesting.

static void swap(char* lo, char* hi) {
  char tmp = *hi;
  *hi = *lo;
  *lo = tmp;
}

static char* step(char* tortoise, char* hare) {
  if (hare[0]) return tortoise;
  if (hare[1]) return tortoise + 1;
  hare = step(tortoise + 1, hare + 2);
  swap(tortoise, hare);
  return hare + 1;
}

void reverse_in_place(char* str) { step(str, str); }

---

Note 1: The "there and back again" pattern comes from a paper by Olivier Danvy and Mayer Goldberg, which makes for fun reading. The paper still seems to be online at ftp://ftp.daimi.au.dk/pub/BRICS/pub/RS/05/3/BRICS-RS-05-3.pdf

Answer 2

"Reversing a string recursively" is a very vague statement of a problem, which allows for many completely different solutions.

Note that a "reasonable" solution should avoid making excessive passes over the string. Any solution that begins with strlen is not really a reasonable one. It is recursive for the sake of being recursive and nothing more. If one resorts to making an additional pass over the string, one no longer really needs a recursive solution at all. In other words, any solution that begins with strlen is not really satisfactory.

So, let's look for a more sensible single-pass recursive solution. And you almost got it already.

Your code already taught you that the reverse sequence of characters is obtained on the backtracking phase of recursion. That's exactly where you placed your printf. So, the "straightforward" approach would be to take these reversed characters, and instead of printf-ing them just write them back into the original string starting from the beginning of the string. A naive attempt to do this might look as follows

void reversestring_impl(char* s, char **dst)
{
  if (*s != '\0')
  {
    reversestring_impl(s + 1, dst);
    *(*dst)++ = *s;
  }
}

void reversestring5(char* s)
{
  char *dst = s;
  reversestring_impl(s, &dst);
}

Note that this implementation uses an additional parameter dst, which carries the destination location for writing the next output character. That destination location remains unchanged on the forward pass of the recursion, and gets incremented as we write output characters on the backtracking pass of the recursion.

However, the above code will not work properly, since we are working "in place", i.e. using the same string as input and output at the same time. The beginning of the string will get overwritten prematurely. This will destroy character information that will be needed on later backtracking steps. In order to work around this issue each nested level of recursion should save its current character locally before the recursive call and use the saved copy after the recursive call

void reversestring_impl(char* s, char **dst)
{
  if (*s != '\0')
  {
    char c = *s;
    reversestring_impl(s + 1, dst);
    *(*dst)++ = c;
  }
}

void reversestring5(char* s)
{
  char *dst = s;
  reversestring_impl(s, &dst);
}

int main()
{
  char str[] = "123456789";

  reversestring5(str);

  printf("%s\n", str);
}

The above works as intended.

Answer 3

This is a good question, and the answer involves a technique that apparently few people are familiar with, judging by the other answers. This does the job ... it recursively converts the string into a linked list (kept on the stack, so it's quite efficient) that represents the reversal of the string. It then converts the linked list back into a string (which it does iteratively, but the problem statement doesn't say it can't). There's a complaint in the comments that this is "overkill", but any recursive solution will be overkill ... recursion is simply not a good way to process an array in reverse. But note that there is a whole set of problems that this approach can be applied to where one generates values on the fly rather than having them already available in an array, and then they are to be processed in reverse. Since the OP is interested in developing or brushing up on skills, this answer provides extra value ... and because this technique of creating a linked list on the stack and then consuming the linked list in the termination condition (as it must be, before the memory of the linked list goes out of scope) is apparently not well known. An example is backtrack algorithms such as for the Eight Queens problem.

In response to complaints that this isn't "pure recursive" because of the iterative copy of the list to the string buffer, I've updated it to do it both ways:

#include <stdio.h>
#include <stdlib.h>

typedef struct Cnode Cnode;
struct Cnode
{
    char c;
    const Cnode* next;
};

static void list_to_string(char* s, const Cnode* np)
{
#ifdef ALL_RECURSIVE
    if (np)
    {
        *s = np->c;
        list_to_string(s+1, np->next);
    }
    else
        *s = '\0';
#else
    for (; np; np = np->next)
        *s++ = np->c;
    *s = '\0';
#endif
}

static char* reverse_string_recursive(const char* s, size_t len, const Cnode* np)
{
    if (*s)
    {
        Cnode cn = { *s, np };
        return reverse_string_recursive(s+1, len+1, &cn);
    }

    char* rs = malloc(len+1);
    if (rs)
        list_to_string(rs, np);
    return rs;
}

char* reverse_string(const char* s)
{
    return reverse_string_recursive(s, 0, NULL);
}

int main (int argc, char** argv)
{
    if (argc > 1)
    {
        const char* rs = reverse_string(argv[1]);
        printf("%s\n", rs? rs : "[malloc failed in reverse_string]");
    }

    return 0;
}

Answer 4

char* reversestring5(char* s){
    size_t len = strlen(s);
    char last[2] = {*s};
    return (len > 1) ? strcat(memmove(s, reversestring5(s+1), len), last) : s;
}

Answer 5

With a recursive function, it's usually easiest to first figure out how to solve a trivial case (e.g. reversing a string with just a pair of characters) and then see how one might divide up the the problem into simple operations culminating with the trivial case. For example one might do this:

This is the actual recursive function:

char *revrecurse(char *front, char *back)
{
    if (front < back) {
        char temp = *front;
        *front = *back;
        *back = temp;
        revrecurse(front+1, back-1);
    }
    return front;
}

This part just uses the recursive function:

char *reverse(char *str)
{
    return revrecurse(str, &str[strlen(str)-1]);
}

Note that this assumes that the pointer is valid and that it points to a NUL-terminated string.

If you're going to actually reverse the characters, you can either provide a pair of pointers and recursively swap letters (which is what this routine does) or copy the characters one at a time into yet another space. That's essentially what your original code is doing; copying each character at a time to stdout which is a global structure that is not explicitly passed but is being used by your routine. The analog to that approach, but using pointers might look like this:

#define MAXSTRINGLEN 200

char revbuf[MAXSTRINGLEN];
char *refptr = revbuf;

char *revstring(char *s)
{
    if (*s != 0)
    {
        revstring(s+1);
        *refptr++ = *s;    /* copy non-NUL characters */
    } else {
        *refptr++ = '\0';  /* copy NUL character */
    }
    return revbuf;
}

In this minor modification to your original code, you can now see the reliance of this approach on global variables revbuf and refptr which were hidden inside stdout in your original code. Obviously this is not even close to optimized -- it's intended solely for explanatory purposes.

Answer 6

If you really can't use a helper function and you really can't modify the interface to the function and you really must use recursion, you could do this, horrible though it is:

char *str_reverse(char *str)
{
    size_t len = strlen(str);
    if (len > 1)
    {
        char c0 = str[0];
        char c1 = str[len-1];
        str[len-1] = '\0';
        (void)str_reverse(str+1);
        str[0] = c1;
        str[len-1] = c0;
    }
    return str;
}

This captures the first and last characters in the string (you could survive without capturing the first), then shortens the string, calls the function on the shortened string, then reinstates the swapped first and last characters. The return value is really of no help; I only kept it to keep the interface unchanged. This is clearest when the recursive call ignores the return value.

Note that this is gruesome for performance because it evaluates strlen() (N/2) times, rather than just once. Given a gigabyte string to reverse, that matters.

I can't think of a good way to write the code without using strlen() or its equivalent. To reverse the string in situ, you have to know where the end is somehow. Since the interface you stipulate does not include the information on where the end is, you have to find the end in the function, somehow. I don't regard strchr(str, '\0') as significantly different from strlen(str), for instance.

If you change the interface to:

void mem_reverse_in_situ(char *start, char *end)
{
    if (start < end)
    {
        char c0 = *start;
        *start = *end;
        *end = c0;
        mem_reverse_in_situ(start+1, end-1);
    }
}

Then the reversal code avoids all issues of string length (or memory length) — requiring the calling code to deal with it. The function simply swaps the ends and calls itself on the middle segment. You'd not write this as a recursive function, though; you'd use an iterative solution:

void mem_reverse_in_situ(char *start, char *end)
{
    while (start < end)
    {
        char c0 = *start;
        *start++ = *end;
        *end-- = c0;
    }
}