自定义list_t中的尾递归函数

Question

我正在从事一个基于C中自定义数据结构list\t的项目。这是可以帮助我操作这个list\t的预定义函数，我被要求编写的函数叫做insert\u list（list\u t，list\u 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中出现的顺序），然后是整个第二个html" target="_blank">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大于零时，保持从第一个元素的前面取下元素，并将其预挂到第二个元素，同时减小n。当n达到零时，执行相反的操作：从第二个元素的前面取下元素，并将其预挂到第一个元素，直到第二个元素为空。这实现了全尾递归实现。

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