递归函数中用变量存s.length()可行，直接调用却报错的原因？

代码示例 #

// recursive function
int helper(string s, int i) {
    int num = 0;
    int len = s.length();
    cout << "i" << i << endl;
    if (i == len) {
        return 1;
    }
    if (s[i] == '0') {
        return 0;
    }
    for (int j = 1; j <= 2; j++) {

        if (len - i - j >= 0) {         // OPTION 1
        // if (s.length() - i - j >= 0) {  // OPTION 2

            string str = s.substr(i, j);
            int n = stoi(str);
            if (n < 27) {
                cout << "call" << i << j << endl;
                num = num + helper(s, i + j); // recursion
            }
        }
    }
    return num;
}

int numDecodings(string s) {
    if (s == "") {
        return 0;
    }
    return helper(s, 0);
}

问题描述 #

在上述C++代码中，len存储了s.length()的值，且s在所有递归调用中均为常量，s.length()的值始终保持一致。为何使用len的OPTION 1可以正常运行，而直接使用s.length()的OPTION 2会报错？

原因解析 #

核心问题是无符号整数溢出导致的条件判断失效：

• s.length()返回的是size_t类型（无符号整数），而i、j是int类型（有符号整数）。当计算s.length() - i - j时，i和j会被隐式转换为size_t类型。如果i + j > s.length()，计算结果本应为负数，但无符号整数无法表示负数，会触发溢出回绕，结果变成一个极大的正数，导致>=0的条件永远为真。
• 此时执行s.substr(i, j)会触发字符串越界访问，因为i + j超出了字符串的实际长度，触发未定义行为（比如程序崩溃、内存访问错误）。

而OPTION 1中的len是int类型（有符号整数），当len - i - j < 0时，条件判断为假，直接跳过后续的substr操作，自然不会触发越界问题。

举个具体例子：假设字符串长度为3，当i=2、j=2时：

• OPTION1：3 - 2 - 2 = -1 >=0为假，跳过后续代码；
• OPTION2：size_t(3) - 2 -2会被当作无符号计算，结果为SIZE_MAX（系统最大无符号整数），>=0为真，执行substr(2,2)，但字符串从索引2开始仅剩余1个字符，直接触发越界报错。

内容的提问来源于stack exchange，提问作者DAKSHTECHIE1