CODEWITHSUNDEEP
crecursion
Impasse
Impasse

Reputation: 105

Trying to understand a recursive function to reverse a string

I can't understand why this code works. Do characters in the string get removed because they are being passed by reference? I see no decrement or such, so I find that really confusing. Also, is the string getting reversed because of the lifo nature of the function call stack?

 void reverse(const char * const sPtr){
   if('\0' == sPtr[0])
     return;
     else{
       reverse(&sPtr[1]);
       putchar(sPtr[0]);
    }
 }

Upvotes: 2

Views: 113

Answers (4)

alinsoar
alinsoar

Reputation: 15793

After the last reverse(&sPtr[1]) there will be stacked 3 calls of putchar.

Each call of reverse grows the pointer with 1, so the stacked calls will be --supposing the input string is made of 3 characters--

CURRENT FRAME -- *(ptr+3) is NULL
putchar(*(ptr+2))
putchar(*(ptr+1))
putchar(*(ptr+0))

Upvotes: 1

klutt
klutt

Reputation: 31306

If you input "abc", the call stack will look something like this.

reverse("abc")
    reverse("bc")
        reverse("c")
        print("c")
    print("b")
print("a")

So each reverse call calls itself with the same string, but first character excluded, and THEN prints the first character in the string.

Do characters in the string get removed because they are being passed by reference?

There is no call by reference in C. Pointers kind of emulate it, but everything in C is passed by value. Besides, the type of the pointer const char * const says two things. First, the pointer will not get reassigned to point at anything else, but more importantly, it also says that the string will not be changed. Try adding the line sPtr[0] = 'a' somewhere, and you'll get a compiler error.

Upvotes: 2

gsamaras
gsamaras

Reputation: 73366

No, it doesn't get deleted.

In every recursive call, you want to progress to the next character, which is done here:

reverse(&sPtr[1]); // you pass a parameter the 1st character of where you point to now

Upvotes: 1

Konrad Rudolph
Konrad Rudolph

Reputation: 545568

Nothing is being removed. But the pointer being passed into the function is changed, in this expression:

&sPtr[1]

… which is equivalent to

sPtr + 1

So each recursive call increments the pointer by one, thus causing the recursive calls to traverse your char array.

As for why this causes the reversal of the string, the LIFO nature of the stack is indeed the reason. Your function first calls itself recursively and then outputs the current character using putchar. This has thus the effect of outputting the characters in reverse order.

Upvotes: 2

Related Questions