时间戳

首页 > 解决方案 > (C) 只需要 1 个参数的递归 strcpy()

c - (C) 只需要 1 个参数的递归 strcpy()

问题描述

让我从一开始就清楚，这不是骗局，我会解释如何。所以，我要求自己编写一个模仿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);
}

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

标签： carraysstringrecursion

解决方案

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

您不会为此任务使用递归是有原因的（您可能知道）：堆栈深度将等于输入字符串的长度，并且推送整个堆栈帧以及复制每个字符的调用指令会产生很多开销。即便如此，如果您真的要递归地执行它，您也不会使用单个参数递归地执行它：您将创建一个声明一些局部变量并调用具有多个参数的递归函数的单参数函数。

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

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

推荐阅读