2

There is this problem on LeetCode that I can not get to work in C/C++
The idea is to reverse an array in its place (using no other additional array) using recursion.
The link is : https://leetcode.com/explore/learn/card/recursion-i/250/principle-of-recursion/1440/
The solution is done in Java or Python.
I tried implementing the solution in C but I always get the original array, my code is as follows:

void reverseString(char* s, int sSize){
    if(!s)
        return;
    reverseString(s+1,sSize-1);
    s[sSize] = *s;
}

There is something I am not accounting for. Please let me know how would you solve it, and if possible why this is not working. Thanks.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
Aelgawad
  • 184
  • 1
  • 16

3 Answers3

5

I'll take a stab at this.

The general idea for a recursive solution is for each call to get a pointer to the start of a string, and how many characters to look at, and this walks its way to the middle of the string.

void reverseString(char *start, int n)
{
    if (n <= 1) return;

    char tmp = start[0];
    start[0] = start[--n];   // the nth character is start[n-1]
    start[n] = tmp;

    reverseString(++start, --n);
}

On each recursive call, the starting string pointer is incremented by one, and the length decreased by two.

FIRST CALL:   v          v
              hello, world
SECOND CALL:   ^        ^

The common danger area is making sure it does the right thing with even and odd-length strings.

This method is a bit simpler with just two parameters, and - as some might say - a bit more elegant :-) even if the ++ and -- could be considered tricky (one increment and two decrements).

EDIT: This version is also tail recursive, which can lead to certain optimizations by internally turning it into a loop.

Steve Friedl
  • 3,929
  • 1
  • 23
  • 30
  • I was about to ask you to write an answer yourself as I was curious about how you'd go about solving this. +1. Aren't increment and decrement operators' behaviors implementation dependent though? – Saucy Goat Dec 21 '19 at 19:27
  • 2
    They're only tricky in that you have to read it closely, but these are all entirely well defined. I just simplified it a bit: still functions the same, but maybe easier to follow. – Steve Friedl Dec 21 '19 at 19:29
  • 1
    Alright, thank you! I'm fairly new to answering questions on SO, but I'm slowly getting the grasp of it thanks to you helpful comment section people. Cheers! – Saucy Goat Dec 21 '19 at 19:31
  • Thank you, that helps me out alot, I was going about it the wrong way – Aelgawad Dec 21 '19 at 22:34
0

Solution (thank you to the folks in the comments):

void reverse(char * str, int len)
{
    char tmp;

    if (len <= 1)
        return;

    tmp = str[0];
    len--;
    str[0] = str[len];
    str[len] = tmp;
    str++;
    reverse(str, len-1);
}

Call this function with your initial string and 0 as arguments:

char str[] = "Ding dong";

reverse(str, 0, strlen(a));
Saucy Goat
  • 1,587
  • 1
  • 11
  • 32
  • @ggorlen I have tested and re-read this code and cannot see where it would fail. Could you please develop on that? – Saucy Goat Dec 21 '19 at 18:45
  • 2
    What is the value of `i` the second time you call it? What happens if it's called by multiple threads? – Steve Friedl Dec 21 '19 at 18:47
  • 1
    @SaucyGoat Call it twice in the same program with different strings. – Schwern Dec 21 '19 at 18:51
  • @SteveFriedl thank you! I edited accordingly, that was a major oversight on my part. Should be okay now. – Saucy Goat Dec 21 '19 at 18:53
  • 1
    @SaucyGoat It works, but `strlen(str)` scans the whole string making it `O(n^2)`. – Schwern Dec 21 '19 at 18:54
  • Corrected @ggorlen – Saucy Goat Dec 21 '19 at 18:58
  • 1
    Now you call `reverse()` with 3 parameters: you could dump the "start" parameter by just incrementing the string pointer on subsequent calls. – Steve Friedl Dec 21 '19 at 18:59
  • @SteveFriedl I don't see how I would do the `if (i == len/2)` confirmation if I don't know in which position of the array I'm in though – Saucy Goat Dec 21 '19 at 19:03
  • @SaucyGoat - Each call would have a pointer to the first character to look at, and the number of characters to consider. Each call would have ptr+1 and len-1 on subsequent recursive visits until len <= 1; – Steve Friedl Dec 21 '19 at 19:05
  • 1
    @SteveFriedl took me longer than I'd like to admit, but I figured out what you meant. Your solution is way more elegant. Cheers :) – Saucy Goat Dec 21 '19 at 19:23
0
void reverse_string(char *x, int start, int end)
{
    char ch;
    if (start >= end)
       return;

    ch = *(x+start);
    *(x+start) = *(x+end);
    *(x+end) = ch;

    //Function calling itself: Recursion
    reverse_string(x, ++start, --end);
}

In this function we are passing the string, the starting index and the ending index.... The recursion will continue till start>=end i.e. till the center of the string appears..... And everytime it will swap the 2 indexes i.e. from the start and from the end...

Guru Prasad mohapatra
  • 1,809
  • 13
  • 19