c++ - 为什么将十进制转换为二进制的递归方法比迭代、使用和返回字符串要快？

Question

我创建了两个接受十进制数字并返回该数字的二进制表示的函数。我选择了一种简单的方法，通过在一些简单的数学运算后将 1 和 0 连接到一个字符串。我创建了一个迭代和递归方法来做到这一点。然后我用老师给我的计时器课对这两种方法进行计时。事实证明，与迭代方法相比，我的递归方法大约快两倍。为什么会这样？

string CConversion::decimalToBinaryIterative(int num)
{
   string ss;
   while(num > 0)
   {
        if  (num%2 != 0)
        {
            ss = '1' + ss;
        }
        else
        {
            ss = '0' + ss;
        }
        num=num/2;
    }
    return ss;
}
string CConversion::decimalToBinaryRecursive(int num)
{
    if(num <= 0)
    { 
        return "";
    } 
    else 
    {
       if  (num%2 != 0)
       {
            return decimalToBinaryRecursive(num/2) + '1';
       }
        else
        {
            return  decimalToBinaryRecursive(num/2) + '0';
        }
    }

}

Answer 1

将一个字符附加到 astd::string比预先附加一个字符便宜，因为如果字符串的容量允许您这样做，则可以在不复制字符串的情况下完成附加。

然而，前置总是需要整个字符串的副本。

如果您将迭代代码更改为此

string ss;
while(num > 0)
{
    if  (num%2 != 0)
    {
        ss = ss + '1';
    }
    else
    {
        ss = ss + '0';
    }
    num=num/2;
 }
 return string(ss.rbegin(), ss.rend());

时间应该几乎相同，或者迭代应该变得更快。

Answer 2

唯一值得怀疑的部分是您如何将字符串连接在一起：

ss = ss + '1';  // 1

ss = '1' + ss;  // 2

第一个（作为递归方法）有机会不移动所有字符，而只是在字符串的末尾添加一个字符。

但是第二个必须将所有字符向右移动（甚至创建一个新字符串）。

要解决此问题，请使用ss += 'x'在函数末尾连接和反转所有字符串。