使用C++中的尾遞歸函數計算列表總和

Question

我正在爲我的大學做作業。我需要創建遞歸函數。

我list_t接口包含以下功能：

List Interface 
The file recursive.h defines the type "list_t" and the following operations on lists: 
// EFFECTS: returns true if list is empty, false otherwise 
bool list_isEmpty​ (const list_t& list); 
// EFFECTS: returns an empty list. 
list_t list_make​(); 
// EFFECTS: given the list (list) make a new list consisting of 
// the new element followed by the elements of the 
// original list. 
list_t list_make​ (int elt, const list_t& list); 
// REQUIRES: list is not empty 
// EFFECTS: returns the first element of list 
int list_first​ (const list_t& list); 
// REQUIRES: list is not empty 
// EFFECTS: returns the list containing all but the first element of list 
list_t list_rest​ (const list_t& list); 
// MODIFIES: cout 
// EFFECTS: prints list to cout. 
void list_print​ (const list_t& list); 

請注意SUM函數必須是尾遞歸，我不能用靜態或全局變量。

到現在爲止我已經跟這個是給了我錯誤的答案：

int sum(list_t list) { 
    if(list.get_rest_list().is_empty()) 
    return list.get_first_elt() + sum(list.get_rest_list()); 
} 

Answer 1

讓我們重寫與正確的縮進該功能：

int sum(list_t list) 
{ 
    if(list.get_rest_list().is_empty()) 
     return list.get_first_elt() + sum(list.get_rest_list()); 

    // what to return here? 
} 

除了有缺陷的邏輯，你不」 t所有控制路徑都覆蓋return語句，如果條件不滿足，會導致返回不確定的值。

（事實並非如此）更正代碼：

int sum(list_t list) 
{ 
    if(list.get_rest_list().is_empty()) 
     return list.get_first_elt(); 

    return list.get_first_elt() + sum(list.get_rest_list()); 
} 

你可以重寫這個使用三元運算符，如果你喜歡。

但是如果你通過一個空的list_t？更好地做到這一點：

int sum(list_t list) 
{ 
    if(list.is_empty()) 
     return 0; 

    return list.get_first_elt() + sum(list.get_rest_list()); 
}