C recursion exercise

Question

How would you solve the following recursion problem?

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

My solution seems pretty ugly to me, and I'm 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 more accurate and elegant solution (which I called the Main solution ) is as follows:

Main decision

 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 gradually build the length of the result. The total parameter does this (not including the NUL terminator). When the recursion completes, the result buffer is allocated once (including the NUL terminator), and then we use recursion to add each copy of s to the result. The main solution works as follows:

• Returns a zero-length string for any number of repetitions of an empty string.
• Returns a zero-length string for zero or negative iterations of a non-empty string.
• Returns a string without zero length for a nonzero positive repeat number 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 result:

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

EDIT: an optimized solution. Read on if you are interested in optimization methods.

---

All other sentences here are mostly executed in O (n ^ 2) and allocate memory at each iteration. Although the Basic Solution is elegant, it uses only one malloc() and accepts only two operators, surprisingly the Basic Solution also has an O (n ^ 2) runtime . This makes it very inefficient if the string s long and means that the basic solution is no more efficient than any other sentence here.

Optimized Solution

The following is an optimal solution to this problem, which 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 another len parameter to cache length s . It recursively uses len to calculate the position in the result buffer where the n copy of s will be placed, so we can replace strcat() with strcpy() each time s to the result. This gives the actual runtime of O (n), not O (n ^ 2).

What is the difference between basic and optimized solutions?

All other solutions used strcat() at least n times in line s to add n copies of s to the result. The problem here is that the strcat() implementation hides inefficiency. Internally strcat() can be thought of as:

 strcat = strlen + strcpy 

ie, when adding, you first need to find the end of the line you are adding before you can make the application. This hidden overhead means that actually when creating n copies of a string, it is necessary to check the length of n and n physical copy operations. However, the real problem is that for every copy of s that we add, our result increases. This means that each subsequent length check inside strcat() on the result also increases. If we compare the two solutions using the “number of times we need to scan or copy s ” as our base for comparison, we can see where the difference lies in the two solutions.

For n copies of string s main solution is 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 Optimized solution works as follows:

 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 main solution performs (n ^ 2 + n) / 2 scans of our string due to the built-in length check in strcat() , whereas the Optimized solution always does (n + 1) scans. This is why the main solution (and any other strcat() runs in O (n ^ 2), while the Optimized solution runs in O (n).

How does O (n) compare with O (n ^ 2) in real life?

Runtime makes a huge difference when using large strings. As an example, let's take the s 1 MB line that we want to create 1000 copies (== 1 GB). If we have a 1 GHz processor that can scan or copy 1 byte / cycle, then 1000 copies of s will be generated as follows:

Note: n is taken from the above performance tables and represents one s scan.

 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, an optimized solution that completes almost instantly destroys the main solution, which takes almost 10 minutes. However, if you think that making the string s less will help, the following result will horrify you. Again, on a machine with a frequency of 1 GHz, which processes 1 byte / cycle, we take s as 1 KB (1,000 times less) and make 1,000,000 copies (total == 1 GB, 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 really an amazing difference. The optimized solution is executed at the same time as before, since the total amount of recorded data is the same. However, Basic Solution comes in half a day , creating the result. This is the difference in runtime between O (n) and O (n ^ 2).

Answer 2

Try this approach when you select a line 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 repetition method should only be used first. (the first one is your prototype)

Note. I have not compiled / tested it, but this should work.

Answer 3

This one is:

 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; } 

We can get someone a tidier code with realloc ()

 char *repeat (char *str, int n) { char *ret_str; if (n == 0) { ret_str = strdup (""); return ret_str; } ret_str = repeat (str, n-1); ret_str = realloc (ret_str, sizeof (char) * strlen (str) * (n + 1)); strcat (ret_str, str); return ret_str; } 

EDIT 1

Ok, this one is more compact .

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

We use a static buffer to store the final string, so one single buffer is used at all levels of recursion.

static int n_top returns the value of the previous value n from recursive calls. This is initialized to -1 to handle the case when called with n = 0 , and thus it returns an empty string (and for which calloc used to initialize with 0). On the first recursive call, the value is -1 , so only at the top level n > n_top true (since n always decreases), in which case the entire buffer is allocated ret_str . Otherwise, we find the lower condition, which, when n becomes 0. At this moment, when n = 0 we return the address of the previously allocated static buffer ret_str parent caller in the recursion tree. This single buffer is then used by each recursion level added by str , and passed to the previous level until it reaches main .

EDIT 2

Even more compact but ugly

 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 last compact code had a problem if you used a call with repeat (str, n); repeat (str, 0); repeat (str, n); repeat (str, 0); . This implementation overcomes this problem and is even more compact using only one function.

Note that there is an ugly one (n=n_top,n_top=0,calloc (sizeof (char), strlen (str) * n + 1)) . Here we guarantee that during the scan we use the n_top value to allocate memory, and then reset n_top to 0 , so that the function has n_top at 0 in the next call from main () or another main caller (not recursive). This can be done in a more readable way, but it looks cool. I would recommend sticking with a more readable one.

EDIT 3

crazy man version

This overcomes the repeated calls to strlen () . strlen () is called only once, and then the string length value along with the n value in the current depth is used to find the offset value, which indicates the end of the returned end string (the address of which is not stored in any intermediate variable, is simply returned and transmitted). When passing a line to memcpy we add the offset and give the original memcpy memory cell by adding offset to the returned response line from the immediately following depth. This actually provides a memcpy location immediately after the end of the line, after which memcpy copies the str material of length str_len . Note that memcpy will return the destination address that was transmitted, that is, the end address of the response string of this depth, but we need the actual start that is achieved by returning offset from this return value, and this is why offset is subtracted before returning.

Note that one function is still used: D

 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); } 

Some notes:

• Perhaps we did offset = str_len * (n-1) , and in this case, at the first depth, str will be copied to offset 0, from the subsequent recursive depths it will copy the string to the response string from the reverse.

• When memcpy executed, we will tell it to copy n bytes, which does not include \0 . But since we use calloc to allocate the final destination memory with space for the terminating character `` \ 0 ', it is initialized to 0. Therefore, the final line will be' \ 0 "complete.

• sizeof (char) is always 1

• To make it more compact and cryptic, remove offset calculations and directly calculate the offset in the last return .

• DO NOT use this code in real life.

Answer 4

This requires a solution that requires a bit more code, but it runs in O (log n) time instead of O (n):

 // Return a string containing 'n' copies of 's' char *repeat(int n, char *s) { return concat((n-1) * strlen(s), strdup(s)); } // Append 'charsToAdd' characters from 's' to 's', charsToAdd >= 0 char *concat(int charsToAdd, char *s) { int oldLen = strlen(s); if (charsToAdd <= n) { // Copy only part of the original string. char *longerString = malloc((oldLen + charsToAdd + 1) * sizeof(char)); strcpy(longerString, s); strncat(longerString, s, charsToAdd); return longerString; } else { // Duplicate s and recurse. char *longerString = malloc((2 * oldLen + 1) * sizeof(char)); strcpy(longerString, s); strcat(longerString, s); free(s); // Free the old string; the recusion will allocate a new one. return concat(charsToAdd - oldLen, longerString); } } 

Answer 5

Possible Solution:

 #include <stdio.h> #include <stdlib.h> #include <string.h> char *repeat(char *s, int n) { static char *sret=NULL; static int isnew=1; if (!s || !s[0]) { if (sret) { free(sret); sret=NULL; } return ""; } if (n<=0) return ""; if (isnew) { int nbuf = strlen(s)*n + 1; sret = (char*)realloc(sret, nbuf); memset(sret, 0, nbuf); isnew=0; } strcat(sret,s); repeat(s, n-1); isnew = 1; return sret; } int main() { char *s = repeat("Hello",50); printf("%s\n", s); s = repeat("Bye",50); printf("%s\n", s); repeat(NULL,0); /* this free the static buffer in repeat() */ s = repeat("so long and farewell",50); printf("%s\n", s); return 0; } 

[edit]
An aps2012 solution that uses one function, but with a static int:

 char *repeat(char *s, int n) { static int t=0; return (n > 0) ? (t += strlen(s),strcat(repeat(s, n - 1), s)) : strcpy(malloc(t + 1), ""); } 

The caller must free() return a string to avoid memory leaks.