编写递归函数，将给定字符串转换为它所表示的数字

Question

在此代码中，我想通过使用recursive function将string转换为integer，但它给出的输出为负。

#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

如果每次调用convert1时都尝试打印s[s.length()]，您将看到它正在打印0。然后减去'0'(48)的值。

假设我们尝试转换"12"。

长度为而不是1，因此在"1"上调用convert1。

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

。因此，如果so为1,s[s.length()]为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 & s，然后可以使用s.pop_back()。作为附带的好处，辅助函数可以很容易地处理以'-'开头的字符串。无论如何，您应该有这个帮助器。

2. 将参数更改为std::string_view，然后它只是一个对字符串的引用，子字符串将缩小该引用。该字符串永远不会被复制。这实际上是唯一的变化，只需将std::string更改为std::string_view，就可以了。

我认为std::string_view是走的路，但需要c++17。将它与处理'-'的帮助器结合使用。

下一个是s[s.length() - 1]，可以写成s.back()。保证了输入的安全性，并且没有出现off-by- 1错误的风险。

则终止递归的条件过于复杂。你可以写

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;
}

---

还有一件事需要考虑，但这是对你的算法的完全重写:

你的递归不是尾部递归。这将占用与字符串长度成比例的堆栈空间。While用于解析"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();