Journey of a simple recursive code

Some one asked the following question in StackOverflow

Implement a function with prototype char *repeat(char *s, int n) so that it creates and returns a string which consists of n repetitions of the input string s. For example: if the input is “Hello” and 3, the output is “HelloHelloHello”. Use only recursive constructs.

I immediately started compiling the answer as it was a pretty straight forward question. But it was not only me who was posting the answer. So after posting, very quickly other answers started appearing. It was a general everyday answer, until a person (who also answered the question) pointed out a bug in my code. Bugs disturb the mind. So I dug into the code and fixed it. The things started to get challenging when others started to get more compact code, which didn’t let me sit idle.

My first version of the function was:

char *repeat (char *str, int n)
{
  char *ret_str, *new_str;

  if (n == 0)
  {
    ret_str = strdup ("");
    return ret_str;
  }
  ret_str = repeat (str, n-1);
  new_str = malloc (sizeof (char) * strlen (str) * n + 1);
  new_str[0] = '\0';
  strcpy (new_str, ret_str);
  strcat (new_str, str);
  free (ret_str);
  return new_str;
}

This function works like this: When you call it with a string and the number of times it needs to be duplicated, it will do down the recursion stack decrementing the value of n at each recursive depth, until n = 0. When this condition is encountered, the recursion starts to roll back, starting from returning a “” that is empty string to the last level of recursion. Therefore if we repeat a string 0 times, the function returns an empty string. While rolling back, at each level ret_str points to a string which has the string (n-1) times repeated. The function allocates one strlen (str) * n + 1 bytes of memory, that is, enough space for repeating the string for the value of n in this level of recursion plus the one byte for the null character. Then it simply copies the returned string to this newly allocated buffer and then concatenates the string str in the argument, repeating the str one more time. The ret_str is not required anymore, therefore it is freed and the newly updated string new_str is returned to the previous level of recursion.

If you call it like

repeat ("Hello", 4);

Then it will return the string “HelloHelloHelloHello”

This used repeated malloc , free and strlen at each level of the recursion therefore not a good one. Compact and efficient answers started being posted by others, therefore i had to give some time to it, inorder to get a compact looking and correct answer. After some thinking i wrote this piece of code:

char *repeat (char *str, int n)
{
  static char *ret_str = NULL;
  static int n_top = -1;

  if (n >= n_top)
  {
    free (ret_str);
    ret_str = calloc (sizeof (char), strlen (str) * n + 1);
  }
  if (n <= 0)
    return strcpy (ret_str, "");

  n_top = n;

  return strcat (repeat (str, n-1), str);
}

This code uses a static buffer to hold the final string, therefore one single buffer is used throughout in all the levels of recursion, omitting the need for repeated calls of malloc and free. calloc is used, so that the I don’t have to write that ret_str[0] = '' line.

The static int n_top holds the value of the previous value of n from recursive calls. This is initialized by -1 to handle the case when called with n = 0, and thus it returns an empty string (and for which calloc is used to initialize with 0). At the first recursive call the value is -1 therefore only at the top level n > n_top is true (as n is always decreasing), and in this case the entire buffer is allocated ret_str. Before we allocate the buffer we free any previous allocated buffer from the previous iteration (or for the first time ret_str is NULL). Else we find for the bottom condition, which is when n becomes 0. At this point when n = 0 and so we return the address of the pre-allocated static buffer ret_str, copying an empty string into it, to the parent callers in the recursion tree. This single buffer is then used by each level of recursion appended by str and handed over to the previous level, until it reaches the main (or other caller).

Instead of making the ugly trick of creating a static buffer and allocating it in an ugly way in one function, I could have just allocated the buffer in a function, and then called another function passing this allocated buffer and the original string and the number of times to concatenate to get the job done, but the challenge was to write a single function. (Checkout the codes posted by others in the StackOverflow on the question).

Although this overcame the problems in the previous versions, someone posted a shorter code and wouldn’t let me rest. So, again I started thinking about compacting the code, which resulted in the following:

char *repeat (char *str, int n)
{
  static int n_top;
  n_top = (n_top == 0)? n: n_top;
  return (n <= 0)?(n=n_top,n_top=0,calloc (sizeof (char), strlen (str) * n + 1)):strcat (repeat (str, n-1), str);
}

The return statement looks really ugly, but it works. This is basically a compact version of the previous code. The line n_top = (n_top == 0)? n: n_top; catches the initial value of n with which it was called from the main (or other) function. As n_top is static, it is initialized with 0, and therefore will be assigned to the value of n at the very first call of this function, and therefore hold the initial value of n. This value is used to allocate the buffer at the bottom level of recursion.

Now let us go to the next line. Which is

return (n <= 0)?(n=n_top,n_top=0,calloc (sizeof (char), strlen (str) * n + 1)):strcat (repeat (str, n-1), str);

This has a ternary operator, which is basically the following structure.

if (n <= 0)
{
  n = n_top;
  n_top = 0;
  return calloc (sizeof (char), strlen (str) * n + 1);
}
else
  return strcat (repeat (str, n-1), str);

That is: when the recursion has reached the leaf, then using the value of n_top buffer is allocated using calloc and returned. Also note that the value of n_top reinitialized to 0 at the leaf level, so that when we call the repeat function again from main (or some other top level function), it works properly (requires that n_top is 0 at top level of recursion to set the value of n as described above).

Oh! for those, who doesn’t use much, the comma operator, it will evaluate the left to right. The evaluation of the expression would be the value of the rightmost statement.

This can be done in more readable way, but this looks cool. I would recommend to stick with a more readable one.

This did not stop the quest. Someone complained about the repetitive call of strlen. So here I pulled out another version of the code, after around a painful 20 minutes, which omits the repetitive calls of strlen

char *repeat (char *str, int n)
{
  static int n_top, str_len;
  int offset = 0;

  (n_top == 0)?(n_top = n,str_len = strlen (str)):(offset = str_len * (n_top-n));
  return (n <= 0)?(n=n_top,n_top=0,malloc (str_len * n + 1)):(memcpy (repeat (str, n-1) + offset, str, str_len) - offset);
}

Omits repetitive calls of repetitive strlen, but the code readability is worse than before, here is how it works.

strlen is called only once, and then the value of the string length along with the value of n in the current depth is used to find the offset value which indicates the end of the final string being returned (whose address is not stored in any intermediate variable, just returned and passed). When passing the string to memcpy we add the offset and give the exact location from which memcpy should place a copy of str to the returned answer string from the immediately below depth. This actually provides memcpy the location immediately after the string end (not the buffer end), after which memcpy copies the stuff str of length str_len. Note that memcpy will return the destination address which it was passed, which is the answer string end address of this depth, but we need the actual beginning, which is achieved by going back offset from this returned value, and that is why offset is subtracted before returning.

I couldn’t believe this really, actually worked.

Here are some notes which i also mentioned in my stackoverflow answer

• I may have made offset = str_len * (n-1) in which case in the first depth the str would be copied in offset 0, from subsequent recursive depths it would copy the string to the answer string from reverse.
• When doing memcpy we tell it to copy n bytes, which does not include . But as we use calloc to allocate the final destination memory with the space for the terminating '' character, it is initialized to 0. Therefore the final string will be '' terminated.
• sizeof (char) is always 1
• To make it look more compact and cryptic remove offset calculation and directly calculate the offset in the last return expression.
• DO NOT use this code in real life. (most important)

Although the last note is the most important one, but I actually like the last version of the code, because it uses only one short function and gets the job done :) .

Please comment to point to existing bugs in the code and/or to share a shorter, better code?

Reference

• My answer in StackOverflow: Exercise on recursion in C