Recursion with C

Question

I have the code below for reversing the string reversal, it works when I print the characters after the recursion is complete, but I cannot figure out how to collect the reverse characters in the string and return them back to the caller. Does anyone have an idea? I don’t want to add another parameter in order to accumulate characters, that’s right, this is not homework, I am combing the little things, as I will be finishing the year and should succeed well in the interview.

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

With a recursive function, it is usually easier to first figure out how to solve the trivial case (for example, flip a line with only two characters), and then see how you can divide the problem into simple operations that culminate in the trivial case. For example, you can 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 a recursive function:

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

Note that this assumes the pointer is valid and points to the NUL string.

If you are going to actually flip characters, you can specify a pair of pointers and a recursive substitution of letters (which this procedure does) or copy the characters one at a time to another space. This is what your source code does; copying each character at a time to stdout , which is a global structure that is not explicitly passed, but used by your program. An analogue of this 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 of the source code, you can now see the dependence of this approach on the global variables revbuf and refptr , which were hidden inside stdout in the source code. Obviously, this is not even closely optimized - it is intended solely to explain the goals.

Answer 2

"Reversing Reversing String" is a very vague description of a problem that allows you to use many completely different solutions.

Please note that a “smart” solution should avoid excessive line breaks. Any solution starting with strlen is not really reasonable. It is recursive for the sake of recursion and nothing more. If someone resorts to an extra pass over the line, then a recursive solution is no longer required at all. In other words, any solution starting with strlen is not really satisfactory.

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

Your code has already taught you that the reverse character sequence is obtained at the reverse recursion stage. This is where you posted your printf . Thus, a “simple” approach would be to take these inverse characters, and instead of printf , just write them back to the original line, starting at the beginning of the line. A naive attempt to do this might look like this

 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 the optional dst parameter, which carries the destination for writing the next output character. This destination remains unchanged in the forward recursion pass and increments when writing output characters on the recursion return path.

However, the above code will not work properly, since we work "in place", that is, using the same line as the input and output at the same time. The beginning of the line will be overwritten prematurely. This will erase the character information that will be needed in the subsequent stages of the return. To work around this problem, each nested recursion level must 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

If you really can't use a helper function, and you really can't change the interface to the function, and you really have to use recursion, you can do it horribly, although this 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 can survive without capturing the first), then shortens the string, calls a function on the shortened string, and then restores the replaced first and last characters. The return value does not really help; I just saved it so that the interface remains unchanged. This is clearer when the recursive call ignores the return value.

Note that this is terrible for performance, because it evaluates strlen() (N / 2) times, not just once. This means that for a gigabyte string this is important.

I can't think of a good way to write code without using strlen() or its equivalent. To flip a line in place, you need to know where the end is in some way. Since the interface you are specifying does not include information about where the end is located, you must somehow find the end of the function. I don't think strchr(str, '\0') significantly different from strlen(str) , for example.

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 cancellation code avoids all the problems of line length (or memory length) by requiring the calling code to deal with it. The function simply ends up and calls itself in the middle segment. However, you will not write this as a recursive function; you should use an iterative solution:

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

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

This is a good question, and the answer includes a technique that few seem to be familiar with, judging by the other answers. This does the job ... it recursively converts the string into a linked list (stored on the stack, so it is pretty efficient), which is a string change. It then converts the linked list back to a string (which is iterative, but the problem statement does not say that it cannot). There is a complaint in the comments that it is "outsmarting", but any recursive solution would be redundant ... recursion is simply not a good way to process the array in the reverse order. But note that there are a number of problems that can be applied to this approach to where everyone generates values ​​on the fly, and not that they are already available in the array, and then they should be processed in reverse order. Since the OP is interested in developing or improving skills, this answer provides added value ... and because this method of creating a linked list on the stack and then consuming the linked list in an end state (as it should be, until the memory of the linked list goes beyond) apparently not very well known. An example is the return algorithm, for example, for a problem with eight crowns.

In response to complaints that this is not “purely recursive” due to an iterative copy of the list into a string buffer, I updated it to do this in both directions:

 #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 6

Here “over and over” [Note 1] in place, which:

• does not use strlen() and should not know how long the string will be in advance; and

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

It also never supports an iterator, so if it is written in C ++, it can use a forward iterator. However, this function is less interesting because it stores iterators on the stack and requires that you can move forward from the iterator sequentially, so it cannot use input iterators. However, this means that it can be used for inverse values ​​in place in a singly linked list, which is perhaps a little 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 round-trip pattern stems from Olivier Danvey and Mayer Goldberg's paper, which makes reading interesting. The document is still online ftp://ftp.daimi.au.dk/pub/BRICS/pub/RS/05/3/BRICS-RS-05-3.pdf