如何使這個遞歸函數運行得更快？

-1

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顯示慢得多。關於如何讓它跑得更快的任何想法？如何使這個遞歸函數運行得更快？

來源

2016-05-14 user5824263

我不能在你的例子中發現任何遞歸。 –

「這個遞歸函數」？目前沒有遞歸函數。 – MikeCAT

那麼，你在面試時是怎麼做的，你在哪裏被問到這個問題？ –

-1

你不需要任何遞歸，除了是相當平凡的位操作方面實現的：

#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;我只證明它是正確的，沒有嘗試過。

來源

2016-05-14 06:42:20 o11c

我沒有看到這段可怕的代碼如何解決OP使用遞歸函數添加數字的問題。 – sim642

恭喜。你已經成功地在代碼中創建了一個鏈式全加器！我看到優化的潛力，但這個評論領域相當小... – Sylwester

首先，您的解決方案有兩個原因是錯誤的。你不使用遞歸，而是使用循環。

至於爲什麼它運行在後兩種情況如此緩慢：每當b爲負，b遞減一路下跌到最低可能的整數，然後將它纏繞最大可能整數，最後它遞減直到它爲0.假設一個32位整數，你將有大約40億次迭代循環。

您需要區分b的負值和正值，然後根據需要遞減或遞增a。

來源

2016-05-14 07:22:06 Markus

如何使這個遞歸函數運行得更快？

回答

相關問題