c - (C) 仅采用 1 个参数的递归 strcpy()

Question

让我从一开始就明确，这不是一个骗局，我会解释一下。因此，我要求自己编写一个模仿 strcpy 的函数，但有两个条件:

1. 它需要递归
2. 它必须采用单个参数(即原始字符串)

该函数应返回指向新复制的字符串的指针。这就是我到目前为止所尝试过的:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char * my_strcpy(char *original);

int main(void) {
  char *string = my_strcpy("alpine");
  printf("string = <%s>\n", string);
  return 0;
}

char * my_strcpy(char *original){
  char *string = (char *)malloc(10);
  if(*original == '\0') {
    return string;
  }
  *string++ = *original;
  my_strcpy(original + 1);
}

问题有点明显，每次调用 my_strcpy() 时，string 都会被 malloc 编辑。我能想到的解决方案之一是仅在第一次调用函数时为 string 分配内存。由于只允许我有 1 个参数，所以我唯一能想到的就是检查调用堆栈，但我不知道这是否允许，而且确实感觉像作弊。这个问题有逻辑的解决方案吗？

Answer 1

您将其写为尾递归，但我认为在不使函数不可重入的情况下，您唯一的选择是使函数头递归并在递归调用的返回值上重复调用 realloc 来扩展它，然后添加一个字符。这与仅调用 strlen 进行分配具有相同的问题:它在每次递归调用中对输入字符串的长度进行线性处理，结果是隐式 n 平方算法 (0.5*n*(n+1 ))。您可以通过提高摊余时间复杂度、将字符串扩展一个因子并仅在现有缓冲区已满时才增长它来改进它，但这仍然不是很好。

您不使用递归来完成此任务是有原因的(您可能知道):堆栈深度将等于输入字符串长度，并且推送的整个堆栈帧和复制的每个字符的调用指令会很多。高架。即便如此，如果您真的要递归地执行此操作，则不会使用单个参数递归地执行此操作:您将创建一个单参数函数来声明一些局部变量并调用具有多个参数的递归函数。

即使使用 realloc 技巧，也很难或不可能计算原始文件中的字符数，以便您可以适本地调用 realloc，请记住其他 stdlib“str*”函数是禁止使用的，因为它们会可能会使你的整个函数成为 n 平方，我认为我们试图避免这种情况。

可以使用诸如验证字符串是否与指针一样长以及通过 memcpy 用指针替换前几个字符之类的丑陋技巧，使递归的基本情况更加复杂，但是，嗯，恶心。