编写递归功能将给定的字符串转换为代表的数字

Question

在此代码中，我想通过使用递归函数将字符串 转换为整数，但它在Negetive中给出了输出。

#include <iostream>

using namespace std;

int convert1(string s) {
    if (s.length() == 1) {
        int i = s[0] - '0';
        return i;
    }

    int so = convert1(s.substr(0, s.length() - 1));
    int num = s[s.length()] - '0';
    int ans = so * 10 + num;
    return (int)ans;
}

int main()
{
    string s;
    cin >> s;
    cout << convert1(s) << endl;
}

Answer 1

如果您尝试打印s [s.length（）]每次调用convert1时，您会发现它是打印0。然后，您从中减去'0''的值（48）。

假设我们尝试转换“ 12”。

长度是不是 1，因此我们调用convert1 on “ 1”。

是长度1的，所以我们返回1。

因此，如果so是1，并且s [s.length（）] is 0，则num是-48和so * 10 + num评估1 * 10-48是-38。

对于两个数字的输入，您将始终看到第一个数字时间10，减48。对于三位数的数字，您会看到（第一个数字 * 10负48）乘以10个减去48。此模式继续进行。如果第一个数字足够大，则乘以10个减去48的数字会产生正数。如果足够大，正面数字会继续通过递归传播。如果它们的变小大于48，那么一旦结果为负，它将变得更大，因为负数会更递归呼叫。

---

与您做事的方式相反，您可以在Convert1中使用累加器参数。

int convert1(string s, int acc=0) {
    if (s.length() == 1) {
        return acc * 10 + (s[0] - '0');
    }

    return convert1(s.substr(1, s.length() - 1), 
                    acc * 10 + (s[0] - '0'));
}

每次递归调用该函数时，我们都会通过将其乘以10并添加第一个数字的值来更新累加器，并通过取下字符串的“尾巴”来更新字符串。

或者更好，但与原始内容相距甚远，我们在字符串为空时返回累加器。

int convert1(string s, int acc=0) {
    if (s.empty()) return acc;

    return convert1(s.substr(1, s.length() - 1), 
                    acc * 10 + (s[0] - '0'));
}

此尾部递归的好处是，此功能（如果由像样的编译器正确优化）可以在恒定的堆栈空间中运行。尽管在这种情况下是学术性的，因为int类型将在堆栈溢出之前溢出。

Answer 2

正常的递归方式

int main()
{
    string s;
    cin >> s;
    cout << strtol(s.c_str(), nullptr, 10) << endl;
}

由于某种原因，

int convert_string(const char* string, int length){
   if (length == 0) {
      return 0;
   }

   int output = string[0] - '0';
   output *= pow(10, length - 1);
   output += convert_string(&string[1], --length);
   return output;
}

int main()
{
    std::string s;
    std::cin >> s;
    std::cout << convert_string(s.c_str(), s.length()) << std::endl;
}

Answer 3

计算最后一个数字时，

int num = s[s.length()] - '0';

您将对字符串的范围访问。将其更改为

int num = s[s.length() - 1] - '0';

，您的代码有效。效率低下。

您可以在每次递归中创建一个新的子字符串。有两种改进的方法：

1. 制作一个辅助功能，可以使字符串的副本复制，然后调用递归功能。递归功能采用std :: String＆amp; S然后可以使用s.pop_back（）。作为一方面，助手功能可以轻松处理以“ - ”开头的字符串。无论如何，你应该有这个助手。

2. 将参数更改为std :: string_view然后，它只是字符串中的引用，子字符串只会收缩该引用。字符串从未复制。实际上，这是唯一的变化，只需更改std :: String std :: String_view and done。

我认为std :: string_view是要走的方法，但需要C ++ 17。将其与助手相结合，以处理“ - ”。

接下来的事情是s [s.length（）-1]，可以写为s.back（）。可以保管一些打字，没有逐个错误的风险。

那么您终止递归的状况过于复杂。您可以

if (s.empty()) return 0;

以额外的递归电话为代替编写。另一方面，这允许解析“”。不确定哪种方式更快，更简单的测试可能会平衡额外的递归调用。我喜欢它，因为它不会重复数字转换代码，而是键入的较少。

接下来，如果您使用std :: String_view，则s.substr（0，s.length（） - 1）可以更改为使用s.remove_suffix（1）;。

所有这些结合在一起给了您：

int convert1(std::string_view s) {
    if (s.empty()) return 0;

    int num = s.back() - '0';
    s.remove_suffix(1);
    int so = convert1(s)
    int ans = so * 10 + num;
    return ans;
}

---

要考虑的还有一件事，但这是您算法的完整重写：

您的递归不是尾部递归。这消耗了与字符串长度成比例的堆栈空间。在解析“ int”时，这不是一个问题，这将是更大问题的问题。或者，如果有人进入一个非常大的数字“ 14654645656348756 ... 65464”。

要解决这个问题，您必须扭转算法。与其像迭代性那样从前面切碎数字，将它们从前面带走：

int iterative_convert(const std::string &s) {
    int acc = 0;
    for (const auto c : s) acc = acc * 10 + (c - '0');
    return acc;
}

要使此递归您必须将中间结果传递给累积递归。因此，它变成了：

int convert1(std::string_view s, int acc = 0) {
    if (s.empty()) return acc;
    acc = 10 * acc + (s.front() - '0');
    return convert1(s.substr(1), acc);
}

不确定您是如何提出背对面算法的，但是前后会产生更好的代码。

注意：缺少需要C ++ 17，或者如果您愿意，也可以使用std :: String :: const_iterator（需要将s.cend（）作为额外参数）或良好的旧const char *p = s.c_str（）;