我正在基于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，该列表包含第一个list_t中的前n个元素(在(它们在原始list_t中出现的顺序)，然后是整个第二个list_t，然后是第一个list_t的其余元素(整数)。约束条件是此函数及其辅助函数(如果有)必须是尾递归的。在此处查看insert_list()的原型(prototype):
/*
* 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的函数，但是我无法反转一部分列表，只能反转整个列表，并且它不适合我提出的尾递归结构。我还想知道我是否需要编写两个相互依赖的递归函数，但在此途中也没有提出任何有用的解决方案。
最佳答案
您需要继续从第一个列表中添加元素，并递减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);
}
}