鉴于b总是非零,为什么`b？--b:++ b`有效,但`--b`没有？

Question

我试图使用递归来乘以两个整数,并且意外地编写了这段代码:

//the original version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b ); //accident
}

我说,我意外地写了这个,因为我打算写:

b > 0 ? --b : ++b 代替 b ? --b : ++b

我意识到我打算写的东西不会起作用.但令我惊讶的是,我不打算写的东西确实有效.

现在,我注意到它b ?--b : ++b基本上相当于--b因为b在else-block中保证不为零.所以我修改了上面的代码,替换b?--b:++b为--b,如下所示:

//the modified version
int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b); //modification here
}

由于原始版本已经出现,我预计修改后的版本也可以使用.但令我惊讶的是,它不起作用!

• 修改后的版本有什么问题？
• 它不等同于原始版本吗？
• 是--b不是等于b ?--b : ++bIF b非零？如果它是等价的,那么为什么第一个代码可以工作但第二个代码没有呢？

注意:这里,通过"工作",我的意思是它给出了正确的输出.也就是说,它给出了传递给函数的整数的乘法.

Answer 1

它不起作用.我不知道吸烟是什么意思,代码会溢出堆栈.

编辑

在gcc 4.6.0上尝试过 - segfault(由于堆栈溢出).但是-O2,如果你启用了优化,那么确实"它有效".总之:它是偶然的,取决于编译器在幕后的作用.

g++ -g -Wall -o f f.cpp # stack overflow
g++ -O2 -g -Wall -o f f.cpp # "works"

Answer 2

TL; DR版本:打印结果失败的原因是ideone设置了提交代码的时间限制.b? --b: ++b--bSIGXCPU 一个版本得到更好的优化,并在允许的时间内完成.另一个版本给出完全相同的答案,但你不会看到与ideone,因为它运行太慢,并在时间限制内中止.

至于为什么没有发生堆栈溢出,我想在一种情况下编译器必须将递归转换为迭代(这不是尾调用,但它可以简单地转换).

转换的结果将类似于http://ideone.com/AeBYI,它确实给出了正确的结果.通过更高的优化设置,编译器可以在编译时计算结果并在结果代码中存储常量.

Answer 3

下面代码的输出应该给出一个非常强大的线索;)

#include <iostream>

using namespace std;

int multiply(int a, int b)
{
  cout << "a = " << a << "\tb = " << b << std::endl;
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

int main() {
        cout << multiply(12, 7) << endl;
        cout << multiply(12, -7) << endl;
        cout << multiply(-12, -7) << endl;
        cout << multiply(-12, 7) << endl;
        return 0;
}

它看起来像是通过长途跋涉获得答案.

编辑:为了回应下面Nawaz的评论,第一种方法起作用,因为两个补码有符号整数运算的变幻莫测.就像我说的那样,它需要很长的路要走.正如其他人已经指出的那样,由于某些编译器优化或其他原因而启用了它.您可以在下面的代码中看到以前提供的测试输入:

int mul2(int a, int b)
{
    int rv = 0;
    while (b--) rv += a;
    return rv;
}

它实际上应该适用于任何一对整数但在某些情况下需要一些时间才能运行(但我希望你对任何情况下的效率都不感兴趣).

第二种情况不起作用,因为您的条件b > 0 ? --b : ++b实际上转换b为abs(b).也就是说,即使b = -7,您只需在测试用例中添加7次.如果你希望它的表现方式与我认为你希望它表现的方式相反,你需要做的事情如下:

int multiply(int a, int b)
{
  if ( !b )
     return 0;
  else if (b < 0)
     return -a + multiply(-a, -b-1);
  else
     return a + multiply(a, --b);
}

编辑2:试试这个:

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, b ? --b : ++b );
}

和

short multiply(short a, short b)
{
  if ( !b )
     return 0;
  else
     return a + multiply(a, --b);
}

这两个都编译,运行并返回相同(正确)的结果,有或没有优化.正如其他人所指出的那样,您所看到的执行时间差异的原因只能归因于编译器优化代码的方式.您需要分析这两种方法的汇编代码,以确定时间差异的根本原因.