c++ - C++递归中的一个完整的虚拟

Question

大家好，我最近学习了递归，我尝试了很多返回类型，在过去的一两天里，我似乎一直在为这个特定问题而苦苦挣扎。遗憾的是我没有运气。

思路是:

1. 我输入一个值和基数
2. 找到它的第一个余数并将其存储在一个字符串中。
3. 然后用这个值除以底数得到一个新值
4. 重复该过程直到值为 0 或 1，然后返回整个字符串。

代码:

string convert(int value, int b){
    stringstream s;
    //Once the value is 0 or 1 it returns the whole result
    if(value ==0 || value ==1)
        return s.str();
    else
    {
        //I store the remainder results in the stringstream and call the function again
        s<<convert(value/b,b)<<value%b;
    }
}

Answer 1

处理递归时的一个关键时刻是，用户调用的函数递归几乎没有意义。使用递归通常意味着使用递归辅助函数。

/* this is the helper function */
void convert(stringstream& s, int value, int b)
{
    if (value == 0) return;
    convert(s, value / b, b); /* recursive call */
    s << (char)('0' + value % b);
}

/* this is the function the user calls */
string convert(int value, int b)
{
    stringstream s;
    convert(s, value / b, b); /* calls helper, not itself */
    s << (char)('0' + value % b);
    return s.str();
}

现在入口点处理一些特殊情况:

• 个位总是存储，即使是零，所以数字零变成“0”而不是空字符串。
• 入口点创建一个stringstream。
• 入口点获取并返回 stringstream 缓冲区。

这些是您不希望递归函数执行的步骤。在每次递归调用时复制字符串或字符串流是非常浪费的。

此外，stringstream 在这里并不是很有用，因为没有真正的格式化输出发生。所以我会这样做:

void convert(string& s, int value, int b)
{
    if (value == 0) return;
    convert(s, value / b, b); /* recursive call */
    s.append('0' + value % b);
}

/* this is the function the user calls */
string convert(int value, int b)
{
    string s;
    convert(s, value / b, b); /* calls helper, not itself */
    s.append('0' + value % b);
    return s;
}