自定義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); 
    } 
}