क्या यह पूंछ कॉल अनुकूलित हो सकता है? यदि हां, तो इसके लिए विशेष कारण क्या नहीं है?

Question

मैंने जीसीसी 4.8.1 और क्लैंग 3.4.190255 दोनों के साथ कई अनुकूलन स्तरों पर असेंबली आउटपुट की जांच की है, इस तरह के कोड के लिए कोई पूंछ कॉल अनुकूलन नहीं है।

collatz_aux कोई विशेष कारण क्यों पूंछ कॉल अनुकूलन नहीं मिलता है?

#include <vector> 
#include <cassert> 

using namespace std; 

vector<unsigned> concat(vector<unsigned> v, unsigned n) { 
    v.push_back(n); 
    return v; 
} 

vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) { 
    return n == 1 
     ? result 
     : n % 2 == 0 
      ? collatz_aux(n/2, concat(move(result), n)) 
      : collatz_aux(3 * n + 1, concat(move(result), n)); 
} 

vector<unsigned> collatz_vec(unsigned n) { 
    assert(n != 0); 
    return collatz_aux(n, {}); 
} 

int main() { 
    return collatz_vec(10).size(); 
} 

Answer 1

vector<unsigned> पैरामीटर के लिए नाशक लौटने के बाद कहा जाता है की जरूरत है।

Answer 2

आपको इसके लिए पूंछ-कॉल पर भरोसा नहीं करना चाहिए। मुझे लगता है कि यह संभावना नहीं है कि ऑप्टिमाइज़र यह पता लगाने जा रहा है कि दोनों रिकर्सिव कॉल पूंछ-अनुकूलित हो सकते हैं।

यहां एक गैर-पुनरावर्ती संस्करण है।

vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) { 
    while(true){ 
    if(n == 1) return result; 
    result = concat(move(result), n); 
    if(n % 2 == 0) 
    { 
     n=n/2; 
    }else{ 
     n= 3 * n + 1; 
    } 
    } 
} 

Answer 3

बस संदर्भ के लिए, मैं, पुनरावर्ती संस्करण फेरबदल इस पूंछ प्रत्यावर्तन प्राप्त करने के लिए,:

#include <vector> 
#include <cassert> 

using namespace std; 

template<class container> 
container &&collatz_aux(unsigned n, container &&result) { 
    static auto concat = [](container &&c, unsigned n) -> container &&{ 
     c.push_back(n); 
     return forward<container>(c); 
    }; 

    return n == 1 
     ? forward<container>(result) 
     : n % 2 == 0 
      ? collatz_aux(n/2, concat(forward<container>(result), n)) 
      : collatz_aux(3 * n + 1, concat(forward<container>(result), n)); 
} 

vector<unsigned> collatz_vec(unsigned n) { 
    assert(n != 0); 
    return collatz_aux(n, vector<unsigned>{}); 
} 

int main() { 
    return collatz_vec(10).size(); 
}