c++ - 自定义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，然后是第一个 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 的函数，但我无法反转列表的一部分，只能反转整个列表，而且它不适合我提出的尾递归结构。我还想知道我是否需要编写两个实际上相互依赖的递归函数，但也没有想出任何有用的解决方案。

Answer 1

您需要继续添加第一个列表中的元素并递减 n 直到它达到零。然后你需要继续添加第二个列表中的元素，直到用完，最后追加第一个列表的剩余部分。

编辑:上面的描述没有实现尾递归。结果我修改了实现。方法是:当 n 大于零时，继续从 first 前面取出元素并将它们放在 second 之前，同时递减 n。当 n 达到零时，执行相反的操作:继续从 second 前面取出元素并将它们放在 first 之前，直到 第二个 是空的。这实现了完整的尾递归实现。

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