如何使这个递归函数运行得更快？

问题描述：

int add2_recurse(int a, int b) { // recursive 

// Rule: Can't use the *, /, +, =, *=, /=, +=, -= operators. 

// Can use: ++ and/or -- 

// No loops allowed; no static local or global variables. 



// What I have so far 

while(b--) { 
    a++; 
return a; }

int main() { 
show_test(4, "add2", recursive); 
cout << add2_recurse(4,5); cout<<" "; // correct: 9 
cout<<add2_recurse(-5, 15); cout<<" "; // correct: 10 
cout<<add2_recurse(20, -9); cout<<" "; // correct: 11 
cout<<add2_recurse(-7, -5); cout<<" "; // correct: -12 
cout<<endl;

当运行它， “9 10 11 -12” 正确的输出显示，只有11和-12显示慢得多。关于如何让它跑得更快的任何想法？如何使这个递归函数运行得更快？

我不能在你的例子中发现任何递归。 –

“这个递归函数”？目前没有递归函数。 – MikeCAT

那么，你在面试时是怎么做的，你在哪里被问到这个问题？ –

答

你不需要任何递归，除了是相当平凡的位操作方面实现的：

#include <limits.h> /* CHAR_BIT for pedantic correctness */ 

int add(int a_, int b_) 
{ 
    /* 
    Signed types tend to have UB. Prevent this by using unsigned. 
    This might only work with twos-complement systems, sorry - patches welcome. 
    */ 
    const unsigned a = (unsigned)a_; 
    const unsigned b = (unsigned)b_; 
    unsigned s = 0, c = 0; 
    int i; 

    /* constant-sized loop, can be trivially unrolled if you know how many bits are in an int (e.g. 16 or 32) */ 
    for (i = 0; i < sizeof(int) * CHAR_BIT; ++i) 
    { 
     s |= ((a^b^c) & (1 << i)); 
     c = ((a & b) | (a & c) | (b & c)) & (1 << i); 
     c <<= 1; 
    } 

    return (signed)s; 
}

当心上面的代码中的bug;我只证明它是正确的，没有尝试过。

我没有看到这段可怕的代码如何解决OP使用递归函数添加数字的问题。 – sim642

恭喜。你已经成功地在代码中创建了一个链式全加器！我看到优化的潜力，但这个评论领域相当小... – Sylwester

答

首先，您的解决方案有两个原因是错误的。你不使用递归，而是使用循环。

至于为什么它运行在后两种情况如此缓慢：每当b为负，b递减一路下跌到最低可能的整数，然后将它缠绕最大可能整数，最后它递减直到它为0.假设一个32位整数，你将有大约40亿次迭代循环。

您需要区分b的负值和正值，然后根据需要递减或递增a。

如何使这个递归函数运行得更快？

相关推荐