使用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()); 
}