How does this C code work?

Question

I was looking at the following code I came across for printing a string in reverse order in C using recursion:

void ReversePrint(char *str) { //line 1
  if(*str) {                   //line 2
      ReversePrint(str+1);     //line 3
      putchar(*str);           //line 4
  }
}

I am relatively new to C and am confused by line 2. *str from my understanding is dereferencing the pointer and should return the value of the string in the current position. But how is this being used as an argument to a conditional statement (which should except a boolean right?)? In line 3, the pointer will always be incremented to the next block (4 bytes since its an int)...so couldn't this code fail if there happens to be data in the next memory block after the end of the string?

Update: so there are no boolean types in c correct? A conditional statement evaluates to 'false' if the value is 0, and 'true' otherwise?

Answer 1

Line 2 is checking to see if the current character is the null terminator of the string - since C strings are null-terminated, and the null character is considered a false value, it will begin unrolling the recursion when it hits the end of the string (instead of trying to call StrReverse4 on the character after the null terminator, which would be beyond the bounds of the valid data).

Also note that the pointer is to a char, thus incrementing the pointer only increments by 1 byte (since char is a single-byte type).

Example:

 0  1  2  3
+--+--+--+--+
|f |o |o |\0|
+--+--+--+--+

1. When str = 0, then *str is 'f' so the recursive call is made for str+1 = 1.
2. When str = 1, then *str is 'o' so the recursive call is made for str+1 = 2.
3. When str = 2, then *str is 'o' so the recursive call is made for str+1 = 3.
4. When str = 3, then *str is '\0' and \0 is a false value thus if(*str) evaluates to false, so no recursive call is made, thus going back up the recursion we get...
5. Most recent recursion was followed by `putchar('o'), then after that,
6. Next most recent recursion was followed by `putchar('o'), then after that,
7. Least recent recursion was followed by `putchar('f'), and we're done.

Answer 2

At the end of a string is typically a 0 byte - the line if (*str) is checking for the existence of that byte and stopping when it gets to it.

Answer 3

The type of a C string is nothing but a pointer to char. The convention is that what the pointer points to is an array of characters, terminated by a zero byte.

*str, thus, is the first character of the string pointed to by str.

Using *str in a conditional evaluates to false if str points to the terminating null byte in the (empty) string.

Answer 4

at the end of the string there is a 0 - so you have "test" => [0]'t' [1]'e' [2]'s' [3]'t' [4]0

and if(0) -> false

this way this will work

Answer 5

Code at line #2 is used to check '\0' (null) char, which is a string terminator.

Answer 6

In line 3, the pointer will always be incremented to the next block (4 bytes since its an int)...

Thats wrong, this is char *, it will only be incremented by 1. Because char is 1 byte long only.

But how is this being used as an argument to a conditional statement (which should except a boolean right?)?

You can use any value in if( $$ ) at $$, and it will only check if its non zero or not, basically bool is also implemented as simple 1=true and 0=false only.

In other higher level strongly typed language you cant use such things in if, but in C everything boils down to numbers. And you can use anything.

if(1) // evaluates to true 
if("string")  // evaluates to true
if(0) // evaulates to false

You can give any thing in if,while conditions in C.

Answer 7

conditional statements (if, for, while, etc) expect a boolean expression. If you provide an integer value the evaluation boils down to 0 == false or non-0 == true. As mentioned already, the terminating character of a c-string is a null byte (integer value 0). So the if will fail at the end of the string (or first null byte within the string).

As an aside, if you do *str on a NULL pointer you are invoking undefined behavior; you should always verify that a pointer is valid before dereferencing.

Answer 8

1.

str is a pointer to a char. Incrementing str will make the pointer point to the second character of the string (as it's a char array). NOTE: Incrementing pointers will increment by the data type the pointer points to.

For ex:

int *p_int;
p_int++;     /* Increments by 4 */

double *p_dbl;
p_dbl++;      /* Increments by 8 */

2.

if(expression)
{
   statements;
}

The expression is evaluated and if the resulting value is zero (NULL, \0, 0), the statements are not executed. As every string ends with \0 the recursion will have to end some time.

Answer 9

C has no concept of boolean values: in C, every scalar type (ie arithmetic and pointer types) can be used in boolean contexts where 0 means false and non-zero true.

As strings are null-terminated, the terminator will be interpreted as false, whereas every other character (with non-zero value!) will be true. This means means there's an easy way to iterate over the characters of a string:

for(;*str; ++str) { /* so something with *str */ }

StrReverse4() does the same thing, but by recursion instead of iteration.

Answer 10

try out for this particular code,which is as simple as the one which you using..!! int rev(int lower,int upper,char*string) { if(lower>upper) return 0; else return rev(lower-1,upper-1,string); }

Answer 11

yes it work, but first you need to realize it in your mind...

Answer 12

Hi,

This is kind of off topic, but when I saw the question I immediately wondered if that was actually faster than just doing an strlen and iterate from the back.

So, I made a little test.

#include <string.h>

void reverse1(const char* str)
{
    int total = 0;
    if (*str) {
            reverse1(str+1);
            total += *str;
    }
}

void reverse2(const char* str)
{
    int total = 0;
    size_t t = strlen(str);
    while (t > 0) {
            total += str[--t];
    }
}

int main()
{
    const char* str = "here I put a very long string ...";

    int i=99999;

    while (--i > 0) reverseX(str);
}

I first compiled it with X=1 (using the function reverse1) and then with X=2. Both times with -O0.

It consistently returned approximately 6 seconds for the recursive version and 1.8 seconds for the strlen version.

I think it's because strlen is implemented in assembler and the recursion adds quite an overhead.

I'm quite sure that the benchmark is representative, if I'm mistaken please correct me.

Anyway, I thought I should share this with you.