Variable-Less String reverse

Question

In a recent interview, I was asked a very simple question to reverse a string (not just print) without any extra variable and any in-built function. The closest I could think of is:

#include<stdio.h>
#include<string.h>
int main()
{
    char ch[100];
    scanf("%s",&ch);
    int i=0;
    while(i<strlen(ch)/2)
    {
       ch[i]=ch[strlen(ch)-1-i]+ch[i];
       ch[strlen(ch)-1-i]=ch[i]-ch[strlen(ch)-1-i];
       ch[i]=ch[i]-ch[strlen(ch)-1-i];
       i++;
    }
    printf("%s",ch);
    return 0;
}

My solution was rejected as I used variable i. How this is even possible without using a counter variable? Is there any other method to solve this?

EDIT

These were the exact words of question(nothing more or less):

Reverse a string without using any variable or inbuilt functions in C.

Answer 1

Two Three possible implementations: one only prints the string in reverse. Another reverses the string in-memory and in-place. Both assume that defining your own recursive functions is allowed and that parameters don't count as variables. In any case, the parameters themselves are constant, so arguably not variables.

void printRev(const char * const s){
    if(*s != '\0'){ // or just: if(*s){
        printRev(s + 1);
        putchar(*s);
    }
}

Does 'prefix' recursion through the string: first recurse until the end is reached, then print each character after the recursive call returns.

void revStr(char * const s, const int len){
    if(len > 0){
        if(s[0] != s[len]){
            s[0] ^= s[len];
            s[len] ^= s[0];
            s[0] ^= s[len];
        }

        revStr(s + 1, len - 2);
    }
}

Is slightly more involved: it XOR-swaps the 'first' character of the string with the 'last'. Then recurses with the next character as the start of the string, and the length decreased by two. So in the next iteration the second character becomes the first, and the second to last becomes the last character. For this the s pointer itself is still const, but obviously the characters pointed to are modified.

The second function requires the string length as an input parameter, this can also be done (recursively) without needing the built-in strlen function:

int myStrlen(const char * const s){
    if(*s != '\0'){
        return 1 + myStrlen(s + 1);
    }

    return 0;
}

Addit

Here is a version that does not use a length parameter, but requires a disjoint output string, and the input string to be modifiable. It simulates the len - 2 expression from revStr by replacing the last character in src with a NUL-character.

void copyRev(char * const restrict dst, char * const restrict src){
    if(src[0] != '\0'){
        dst[0] = src[myStrlen(src) - 1];
        dst[myStrlen(src) - 1] = src[0];
        src[myStrlen(src) - 1] = '\0';

        copyRev(dst + 1, src + 1);
    }
}

Answer 2

we can re-alloc the string memory to double its size.
we can then memcpy the string to the 2nd half.

e.g. S T R \0 S T R \0

Now we can memcpy 1 char at a time to the original string from the 2nd half.

This is assuming an ascii string with a '\0' terminating char.

void reverseString(const char** pStr)
{
    *pStr = realloc(*pStr, strlen(*pStr)*2 + 2);
    memcpy(*pStr + strlen(*pStr), *pStr, strlen(*pStr));
    while (*pStr)
    {
        memcpy(*pStr, *pStr + strlen(*pStr + 2), 1);
        ++ (*pStr);
    }

}

Answer 3

Using C11's ability to create compound literals as arguments and return values:

typedef struct foo_T {
  char *s;
  char *end;
  char left, right;
} foo_T;

foo_T foo(const foo_T f) {  // No variables, just constant parameter
  if (f.s < f.end) {
    *f.s = f.right;
    *f.end = f.left;
    return (foo_T){f.s+1,f.end-1,*f.s,*f.end};
  }
  return f;
}

char *endptr(char * const s) {  // No variables, just constant parameter
  if (*s == 0) return s-1;
  return endptr(s + 1);
}

void rev_novar(char *s) {
  if (*s && s[1]) {
    foo ((foo_T){s,endptr(s),*s,*endptr(s)});
  }
}

Test

void test_rev(const char *s) {
  char buf[100];
  memset(buf, 77, sizeof buf);
  strcpy(&buf[1], s);
  printf("%d '%s' %d\n", buf[0], &buf[1], buf[strlen(buf) + 1]);
  rev_novar(&buf[1]);
  printf("%d '%s' %d\n\n", buf[0], &buf[1], buf[strlen(buf) + 1]);
}

int main(void) {
  test_rev("123");
  test_rev("1234");
  test_rev("1");
  test_rev("");
  return 0;
}

Test results. (The 77 are left and right sentinels.)

77 '123' 77
77 '321' 77

77 '1234' 77
77 '4231' 77

77 '1' 77
77 '1' 77

77 '' 77
77 '' 77

Answer 4

My guess is that the interviewer got the question wrong. Without any variables, you could have a sequence of hard coded if statements to find the end of the string and then have hard coded swap sequence. It's similar in concept to a sorting network, which is used for sorting a fixed number of values (up to 16, based on wiki article). For example for strings up to length 5:

void reverse(char str[])
{
    if(str[0] == 0 || str[1] == 0)
        return;
    if(str[2] == 0){
        str[0] ^= str[1]; str[1] ^= str[0]; str[0] ^= str[1];
        return;
    }
    if(str[3] == 0){
        str[0] ^= str[2]; str[2] ^= str[0]; str[0] ^= str[2];
        return;
    }
    if(str[4] == 0){
        str[0] ^= str[3]; str[3] ^= str[0]; str[0] ^= str[3];
        str[1] ^= str[2]; str[2] ^= str[1]; str[1] ^= str[2];
        return;
    }
    if(str[5] == 0){
        str[0] ^= str[4]; str[4] ^= str[0]; str[0] ^= str[4];
        str[1] ^= str[3]; str[3] ^= str[1]; str[1] ^= str[3];
        return;
    }
}

Even with the code above, an internal variable (register) is needed for the XOR operations, unless a processor had a xor memory to memory instruction, (the compare to zero can use an immediate constant on X86/X64 processors).

Example code if constant pointers and recursion are allowed, but this essentially uses the stack as multiple instances of variables (the pointers) since they are being manipulated as pointer + 1 and/or pointer - 1 , and since reverse1() is tail recursive, an optimizing compiler will probably convert it into a loop, with beg and end as regular variables.

void reverse0(char * const beg, char * const end);
void reverse1(char * const beg, char * const end);

/* entry function */
void reverse(char str[])
{
    if(str[0] == 0 || str[1] == 0)
        return;
    reverse0(&str[0], &str[2]);
}

/* find end of str */
void reverse0(char * const beg, char * const end)
{
    if(*end != 0){
        reverse0(beg, end+1);
        return;
    }
    reverse1(beg, end-1);           
}

/* reverse str */
void reverse1(char * const beg, char * const end)
{
    *beg ^= *end;
    *end ^= *beg;
    *beg ^= *end;
    if((beg+1) < (end-1))
        reverse1(beg+1, end-1);
}