您将如何解决以下涉及递归的问题？
使用原型实现一个函数， char *repeat(char *s, int n) 以便它创建并返回一个字符串，该字符串由输入字符串 s 的n次重复组成。例如：如果输入是“Hello”和3，则输出是“HelloHelloHello”。仅使用递归构造。
我的解决方案在我看来很丑陋，我正在寻找更清洁的东西。这是我的代码：
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;
}
一个更整洁和优雅的解决方案（我称之为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);
}
这就是递归的美妙之处。该解决方案的关键是使用递归来递增地构建结果的长度。参数total执行此操作（不包括 NUL 终止符）。当递归终止时，结果缓冲区被分配一次（包括 NUL 终止符），然后我们使用递归展开将每个副本附加s到结果中。基本解决方案的行为如下：
如果基于上述函数创建程序，如下语句：
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));
将产生以下输出：
Repeat "" 0 times: []
Repeat "" 3 times: []
Repeat "abcde" 0 times: []
Repeat "abcde" 1 times: [abcde]
Repeat "abcde" 4 times: [abcdeabcdeabcdeabcde]
编辑：优化解决方案如下。如果您对优化技术感兴趣，请继续阅读。
这里的所有其他建议主要在O( n^2 )中运行并在每次迭代时分配内存。尽管基本解决方案很优雅，只使用一个malloc()，并且只需要两个语句，但令人惊讶的是基本解决方案也有 O( n^2 )的运行时间。如果字符串很长，这将使其效率非常低，这s意味着基本解决方案并不比此处的任何其他提议更有效。
优化方案
以下是实际运行在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);
}
如您所见，它现在有三个语句并使用了一个参数len, 来缓存 的长度s。它递归地用于len计算结果缓冲区中第n'th 副本s将被定位的位置，因此允许我们替换strcat()为strcpy()每次s添加到结果中。这给出了O( n ) 的实际运行时间，而不是 O( n^2 )。
基本解决方案和优化解决方案有什么区别？
所有其他解决方案strcat()至少n在字符串上使用了多次以将副本s附加到结果中。这就是问题所在，因为实施隐藏了低效率。在内部，可以认为是：nsstrcat()strcat()
strcat = strlen + strcpy
即，在追加时，您首先必须找到要追加的字符串的结尾，然后才能执行追加本身。这种隐藏的开销意味着，事实上，创建n字符串的副本需要n长度检查和n物理复制操作。然而，真正的问题在于，对于s我们追加的每个副本，我们的结果都会变长。这意味着结果中的每个连续长度检查也strcat()越来越长。如果我们现在以“我们必须扫描或复印的次数”作为比较的基础来比较这两种解决方案，我们可以看到两种解决方案的不同之处在哪里。s
对于nstring 的副本s，基本解决方案执行如下：
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 |
而优化解决方案的执行方式如下：
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 |
从表中可以看出，由于内置的长度检查，基本解决方案对我们的字符串执行 ( n^2 + n)/2 次strcat()扫描，而优化解决方案总是执行(n + 1)次扫描。这就是为什么基本解决方案（以及依赖 的所有其他解决方案strcat()）在O(n^2)中执行，而优化解决方案在O(n)中执行。
O( n ) 与 O( n^2 ) 相比如何？
当使用大字符串时，运行时间会产生巨大的差异。例如，让我们以一个s1MB 的字符串为例，我们希望创建 1,000 个 (== 1GB) 的副本。如果我们有一个 1GHz CPU 可以扫描或复制 1 个字节/时钟周期，那么s将生成 1,000 个副本，如下所示：
注意：n取自上面的性能表，表示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)
如您所见，几乎立即完成的优化解决方案将需要近 10 分钟才能完成的基本解决方案拆除。但是，如果您认为将字符串s变小会有所帮助，那么下一个结果会让您感到恐惧。同样，在处理 1 个字节/时钟周期的 1GHz 机器上，我们取s1KB（小 1000 倍），并制作 1,000,000 个副本（总计 == 1GB，与以前相同）。这给出了：
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)
这是一个真正令人震惊的差异。优化解决方案的执行时间与以前相同，因为写入的数据总量相同。但是，基本解决方案在构建结果时会停滞半天以上。这是 O( n ) 和 O( n^2 )之间运行时间的差异。
尝试这种方法，您只分配一次字符串：
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);
}
第二种重复方法只能由第一种使用。（第一个是你的原型方法）
注意：我没有编译/测试它，但这应该可以。
这是一：
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;
}
我们可以得到看起来更整洁的代码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;
}
编辑 1
好的，这个更紧凑。
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);
}
我们使用一个静态缓冲区来保存最终字符串，因此在所有递归级别中都使用一个缓冲区。
保存来自递归调用static int n_top的前一个值的值。n当用 调用时，它被初始化-1以处理这种情况n = 0，因此它返回一个空字符串（并且用于calloc初始化 0）。因此，在第一次递归调用中，-1只有顶层的值才n > n_top为真（n总是递减），在这种情况下，整个缓冲区都被分配了ret_str。否则我们找到底部条件，也就是whenn变为0。此时n = 0我们将预先分配的静态缓冲区的地址返回给ret_str递归树中的父调用者。然后，这个单个缓冲区被附加的每个递归级别使用str并移交到上一级，直到达到main.
编辑 2
更紧凑的一个，但丑陋
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);
}
如果您使用 call with ，最后一个紧凑代码会出现问题repeat (str, n); repeat (str, 0);。这个实现克服了这个问题，而且它甚至更紧凑，也只使用一个函数。
请注意，有一个丑陋的(n=n_top,n_top=0,calloc (sizeof (char), strlen (str) * n + 1)). 在这里，我们确保在回滚时使用 的值n_top来分配内存，然后重置n_top为，0以便该函数在下一次调用或其他主调用者（非递归）中n_top设置为。这可以以更具可读性的方式完成，但这看起来很酷。我建议坚持使用更具可读性的内容。0main ()
编辑 3
疯子版
这克服了重复strlen ()调用。strlen ()仅调用一次，然后使用字符串长度的值以及n当前深度中的值来查找offset指示返回的最终字符串结束的值（其地址不存储在任何中间变量中，只是返回并通过）。当将字符串传递给我们时，我们添加偏移量并通过从紧接的下一个深度添加到返回的答案字符串来memcpy提供源内存位置。这实际上在字符串结束后立即提供了位置，之后复制了length的东西。注意memcpyoffsetmemcpymemcpystrstr_lenmemcpy会返回它传递的目的地址，也就是这个深度的应答字符串结束地址，但是我们需要实际的开始，这是通过offset从这个返回值返回来实现的，这就是为什么offset在返回之前要减去。
请注意，这仍然使用单一功能：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);
}
一些注意事项：
在这种情况下，我们可能已经完成offset = str_len * (n-1)了在第一个深度str中将在偏移量 0 中复制的情况，从随后的递归深度中，它会将字符串从反向复制到答案字符串。
这样做时，memcpy我们告诉它复制n字节，其中不包括\0. 但是当我们使用calloc为终止字符“\0”分配空间时，它被初始化为0。因此最终的字符串将以“\0”终止。
sizeof (char) 始终为 1
为了使它看起来更紧凑和神秘，删除offset计算并直接计算最后一个return表达式中的偏移量。
不要在现实生活中使用此代码。
这是一个需要更多代码的解决方案，但它运行时间为 O(log n) 而不是 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);
}
}
一个可能的解决方案：
#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's the static buffer in repeat() */
s = repeat("so long and farewell",50);
printf("%s\n", s);
return 0;
}
[编辑]
aps2012 解决方案的变体，它使用单个函数，但使用静态 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), "");
}
调用者必须free()返回字符串以避免内存泄漏。