c - 为什么在递归函数中修剪字符串时会出现段错误？

Question

我必须实现一个函数，根据公式 h_0 = 1337, h_n = h_n-1 * 5 + 计算字符串的哈希 h_N c_n，其中 c_1 和 c_n 是我作业的字符串字符。

我认为递归计算它是一个好主意，但不幸的是，当我尝试删除给定字符串的最后一个字符时，我遇到了段错误。

uint64_t hashString(char *c)
{
    if(strlen(c) == 1) {
        return 1337 * 5 + (int) *c;
    }

    int lc = c[strlen(c) - 1];
    c[strlen(c) - 1] = 0;
    return hashString(c) * 5 + lc;
}

我什至尝试使用memmove，但它什么也没做。我做错了什么？

Answer 1

I thought it would be a great idea to calculate it recursively

不是的!除非您的编译器可以对其进行优化(这涉及尾调用消除作为一个步骤，并且您的实现甚至不是尾递归)，否则每个递归调用都将使用堆栈空间，从而导致堆栈溢出，字符数量相对较少。您当前的实现还

• 为每个字符调用 strlen 多次，这非常慢(二次时间 - 计算哈希所花费的时间与字符串长度的平方成正比)，除非通过优化智能编译器

• 改变其输入，这对于哈希来说是极其不寻常的

改用循环，并确保您的参数是 char const*。

#include "testlib.h"
#include "hash.h"

int main() {
    test_start("hash.c");
    test_equals_int64(hashString("Abc"), result, "hash of A is correct");
    return test_end();
}

...但在此代码中，段错误具体是由于尝试修改只读字符串文字 "Abc" 引起的。如果您的编译器没有就此发出警告，请查找如何启用更多警告。