自定义list_t中的尾递归函数

Question

我正在基于C++中的自定义数据结构list_t的项目工作。 这里是预定义的函数，它可以帮助我操作这个list_t，并且我被要求写入的函数被称为insert_list（list_t，list_t，int）是尾递归的。

typedef Recursive_list list_t; 

// 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); 

的insert_list（）函数我写发生在两者的类型list_t并且保证不大于第一list_t的尺寸更大，并返回包含第一n另一个list_t额外整数n的两个输入来自第一个list_t的元素（按它们出现在原始list_t中的顺序），接着是整个第二个list_t，然后是第一个list_t的其余元素（整数）。约束条件是这个函数及其辅助函数（如果有的话）必须是尾递归的。看到原型insert_list（）位置：

/* 
* REQUIRES: n >= 0 and n <= the number of elements in first 
* EFFECTS: returns a list comprising the first n elements of 
*   "first", followed by all elements of "second", 
*   followed by any remaining elements of "first". 
* 
*  For example: insert ((1 2 3), (4 5 6), 2) 
*   is (1 2 4 5 6 3). 
*/ 
list_t insert_list(list_t first, list_t second, int n); 

我花了几天的思考和尝试的方式来攻击这一点，但我将不得不扭转了前n个数字最远。我确实写了一个可以反转list_t的函数，但是我不能够反转列表的一部分，只能颠倒整个列表，并且它不适合我提出的尾递归结构。我还想知道是否需要编写两个实际上相互依赖的递归函数，但是还没有提出任何有用的解决方案。

Answer 1

您需要不断添加第一个列表中的元素并递减n，直到达到零。然后，您需要继续添加第二个列表中的元素直到它耗尽，最后追加第一个列表的其余部分。

编辑：上面的描述没有实现尾递归。我已经修改了实施结果。方法是：当n大于零时，继续将元素从first开始并预先等待到second，同时递减n。当n达到零时，则做相反的操作：继续将元素从second的前面取走，并将它们预先等待到first，直到second为空。这实现了完整的尾递归实现。

list_t insert_list(list_t first, list_t second, int n) 
{ 
    if(n==0) { 
     if(list_isEmpty(second)) 
      return first; 
     else 
      return insert_list(list_make(list_first(second), first), list_rest(second), 0); 
    } 
    else { 
     return insert_list(list_rest(first), list_make(list_first(first), second), n-1); 
    } 
}