在C中递归练习

Question

你如何解决涉及递归的以下问题？

使用prototype实现一个函数, char *repeat(char *s, int n) 以便创建并返回一个由 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;
}

Answer 1

更加整洁和优雅的解决方案(我称之为基本解决方案)如下:

基本解决方案

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到结果中.基本解决方案的行为如下:

1. 为空字符串的任意数量的重复返回零长度字符串.
2. 返回非空字符串的零或负迭代的零长度字符串.
3. 返回非零长度字符串,表示非空字符串上非零正数的重复次数.

如果基于以上函数创建程序,则以下语句:

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)中运行,并在每次迭代时分配内存.尽管Basic Solution很优雅,只使用一个malloc(),只需要两个语句,但令人惊讶的是Basic Solution的运行时间也是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"的第副本s将被定位,因此使我们能够替换strcat()与strcpy()每个时间s被添加到结果.这给出了O(n)的实际运行时间,而不是O(n ^ 2).

基本和优化解决方案之间有什么区别？

所有其他解决方案strcat()至少n使用字符串s来附加结果的n副本s.这就是问题所在,因为实施strcat()隐藏效率低下.在内部,strcat()可以被认为是:

strcat = strlen + strcpy

也就是说,在追加时,首先必须找到你要追加的字符串的结尾,然后再进行追加.这种隐藏的开销意味着,实际上,创建n字符串的副本需要n长度检查和n物理复制操作.然而,真正的问题在于,对于s我们附加的每个副本,我们的结果会变得更长.这意味着,在每个连续的长度检测strcat()的结果也变得越来越长.如果我们现在使用" 我们必须扫描或复制的次数s "比较两种解决方案作为比较的基础,我们可以看出两种解决方案的区别在哪里.

对于n字符串的副本s,Basic Solution执行如下操作:

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(小1千倍),并制作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)之间运行时间的差异.

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

第二个重复方法只能由第一个重复方法使用。（第一个是你的原型方法）

注意：我没有编译/测试它，但这应该可以工作。