C ++
我正在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的输入和一个额外的整数n，该整数保证不会大于第一个list_t的大小，并返回另一个list_t，其中包含第一个list_t中的前n个元素它们在原始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的函数，但是我不能够反转列表的一部分，只能颠倒整个列表，并且它不适合我提出的尾递归结构。 我还想知道是否需要编写两个实际上相互依赖的递归函数，但是还没有提出任何有用的解决方案。
您需要继续添加第一个列表中的元素并递减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);
}
}
上一篇: c++