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

在处理递归时,一个关键的a-ha时刻是,用户调用的函数几乎从来没有意义递归.使用递归通常意味着使用递归辅助函数.

/* 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缓冲区.

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

此外,字符串流在这里并不真正有用,因为没有真正的格式化输出发生.所以我会这样做:

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