Exercise on recursion in C

Question

How would you solve the following problem involving recursion?

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.

My is solution seems to me quite ugly and I am looking for something cleaner. Here is my code:

char *repeat(char *s, int n) {
  if(n==0) {
     char *ris = malloc(1);
     ris[0] = '\0';
     return ris;
  }
  int a = strlen(s);
  char *ris = malloc(n*a+1);
  char *ris_pre = repeat(s,n-1);
  strcpy(ris,ris_pre);
  strcpy(ris+(n-1)*a,s);
  free(ris_pre);
  return ris;
}

Answer 1

A much more tidy and elegant solution (which I've called Basic Solution) is as follows:

Basic Solution

char *internalRepeat(char *s, int n, size_t total)
{
    return (n > 0)
        ? strcat(internalRepeat(s, n - 1, total + strlen(s)), s)
        : strcpy(malloc(total + 1), "");
}

char *repeat(char *s, int n)
{
    return internalRepeat(s, n, 0);
}

This is the beauty of recursion. The key to this solution uses recursion to incrementally build the length of the result. Parameter total does this (not including the NUL-terminator). When the recursion terminates, the result buffer is allocated once (including the NUL-terminator) and then we use the recursion unwinding to append each copy of sto the result. Basic Solution behaves as follows:

1. Returns a zero-length string for any number of repetitions of an empty string.
2. Returns a zero-length string for zero or negative iterations of a non-empty string.
3. Returns a non-zero-length string for a non-zero-positive number of repetitions on a non-empty string.

If you create a program based on the above functions, the following statements:

printf("Repeat \"\" 0 times: [%s]\n", repeat("", 0));
printf("Repeat \"\" 3 times: [%s]\n", repeat("", 3));
printf("Repeat \"abcde\" 0 times: [%s]\n", repeat("abcde", 0));
printf("Repeat \"abcde\" 1 times: [%s]\n", repeat("abcde", 1));
printf("Repeat \"abcde\" 4 times: [%s]\n", repeat("abcde", 4));

will produce the following output:

Repeat "" 0 times: []
Repeat "" 3 times: []
Repeat "abcde" 0 times: []
Repeat "abcde" 1 times: [abcde]
Repeat "abcde" 4 times: [abcdeabcdeabcdeabcde]

EDIT : Optimised Solution follows. Read on if you're interested in optimisation techniques.

---

All the other proposals here principally run in O(n^2) and allocate memory at every iteration. Even though Basic Solution is elegant, uses only a single malloc(), and takes only two statements, surprisingly Basic Solution also has a running time of O(n^2). This makes it very inefficient if string s is long and means that Basic Solution is no more efficient than any other proposal here.

Optimised Solution

The following is an optimal solution to this problem that actually runs in O(n):

char *internalRepeat(char *s, int n, size_t total, size_t len)
{
    return (n > 0)
        ? strcpy(internalRepeat(s, n - 1, total, len), s) + len
        : strcpy(malloc(total + 1), "");
}

char *repeat(char *s, int n)
{
    int len = strlen(s);

    return internalRepeat(s, n, n * len, len) - (n * len);
}

As you can see, it now has three statements and uses one more parameter, len, to cache the length of s. It recursively uses len to compute the position within the result buffer where the n'th copy of s will be positioned, so allowing us to replace strcat() with strcpy() for each time s is added to the result. This gives an actual running time of O(n), not O(n^2).

What's the difference between the Basic and Optimised solutions?

All other solutions have used strcat() at least n times on string s to append n copies of s to the result. This is where the problem lies, because the implementation of strcat() hides an inefficiency. Internally, strcat() can be thought of as:

strcat = strlen + strcpy

i.e., when appending, you first have to find the end of the string you're appending to before you can do the append itself. This hidden overhead means that, in fact, creating n copies of a string requires n length checks and n physical copying operations. However, the real problem lies in that for each copy of s we append, our result gets longer. This means that each successive length check within strcat() on the result is also getting longer. If we now compare the two solutions using "number of times we have to scan or copy s" as our basis for comparison, we can see where the difference in the two solutions lies.

For n copies of the string s, the Basic Solution performs as follows:

strlen's/iteration: 2
strcpy's/iteration: 1

Iteration | Init | 1 | 2 | 3 | 4 | ... | n |   Total    |
----------+------+---+---+---+---+-----+---+------------+
Scan "s"  |   0  | 1 | 2 | 3 | 4 | ... | n | (n+1)(n/2) |
Copy "s"  |   0  | 1 | 1 | 1 | 1 | ... | 1 |     n      |

whereas the Optimised Solution performs like this:

strlen's/iteration: 0
strcpy's/iteration: 1

Iteration | Init | 1 | 2 | 3 | 4 | ... | n |    Total   |
----------+------+---+---+---+---+-----+---+------------+
Scan "s"  |   1  | 0 | 0 | 0 | 0 | ... | 0 |      1     |
Copy "s"  |   0  | 1 | 1 | 1 | 1 | ... | 1 |      n     |

As you can see from the table, the Basic Solution performs (n^2 + n)/2 scans of our string due to the built-in length check in strcat(), whereas the Optimised Solution always does (n + 1) scans. This is why the Basic Solution (and every other solution that relies on strcat()) performs in O(n^2), whereas the Optimised Solution performs in O(n).

How does O(n) compare to O(n^2) in real terms?

Running times make a huge difference when large strings are being used. As an example, let's take a string s of 1MB that we wish to create 1,000 copies of (== 1GB). If we have a 1GHz CPU that can scan or copy 1 byte/clock cycle, then 1,000 copies of s will be generated as follows:

Note: n is taken from performance tables above, and represents a single scan of s.

Basic:  (n + 1) * (n / 2) + n = (n ^ 2) / 2 + (3n / 2)
                              = (10^3 ^ 2) / 2 + (3 * 10^3) / 2
                              = (5 * 10^5) + (1.5 * 10^2)
                              = ~(5 * 10^5) (scans of "s")
                              = ~(5 * 10^5 * 10^6) (bytes scanned/copied)
                              = ~500 seconds (@1GHz, 8 mins 20 secs).

Optimised: (n + 1)            = 10^3 + 1
                              = ~10^3 (scans of "s")
                              = ~10^3 * 10^6 (bytes scanned/copied)
                              = 1 second (@1Ghz)

As you can see, the Optimised Solution, which completes nearly instantly, demolishes the Basic Solution which takes nearly 10 minutes to complete. However, if you think making string s smaller will help, this next result will horrify you. Again, on a 1GHz machine that processes 1 byte/clock cycle, we take s as 1KB (1 thousand times smaller), and make 1,000,000 copies (total == 1GB, same as before). This gives:

Basic:  (n + 1) * (n / 2) + n = (n ^ 2) / 2 + (3n / 2)
                              = (10^6 ^ 2) / 2 + (3 * 10^6) / 2
                              = (5 * 10^11) + (1.5 * 10^5)
                              = ~(5 * 10^11) (scans of "s")
                              = ~(5 * 10^11 * 10^3) (bytes scanned/copied)
                              = ~50,000 seconds (@1GHz, 833 mins)
                              = 13hrs, 53mins, 20 secs

Optimised: (n + 1)            = 10^6 + 1
                              = ~10^6 (scans of "s")
                              = ~10^6 * 10^3 (bytes scanned/copied)
                              = 1 second (@1Ghz)

This is a truly shocking difference. Optimised Solution performs in the same time as before as the total amount of data written is the same. However, Basic Solution stalls for over half a day building the result. This is the difference in running times between O(n) and O(n^2).

Answer 2

Try this approach where you allocate the string only once :

char *repeat(char *s, int n) {
   int srcLength = strlen(s);
   int destLength = srcLength * n + 1;      
   char *result = malloc(destLength);
   result[0] = '\0'; // This is for strcat calls to work properly

   return repeatInternal(s, result, n);
}

char *repeatInternal(char *s, char *result, int n) {
  if(n==0) {
     return result;
  }

  strcat(s, result);  
  return repeat(result, s, n-1);
}

The second repeat method should be used only by the first one. (the first one is your prototype method)

Note : I did not compile/test it but this should work.