Tail-Recursive-Funktion in selbstdefinierten list_t

Question

Ich arbeite an einem Projekt basierend auf einer benutzerdefinierten Datenstruktur list_t in C++. Hier sind die vordefinierten Funktionen, die mir helfen würden, diese list_t zu manipulieren, und die Funktion, die ich schreiben soll, heißt insert_list (list_t, list_t, int) soll tail-rekursiv sein.

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

Die insert_list() Funktion Ich bin nimmt beide vom Typ list_t und eine zusätzliche ganze Zahl n in zwei Eingängen zu schreiben, die nicht größer als die Größe des ersten list_t gewährleistet ist und eine andere list_t zurückgibt, der die erste n enthält Elemente aus der ersten list_t (in der Reihenfolge, in der sie in der ursprünglichen list_t erscheinen), gefolgt von der gesamten zweiten list_t gefolgt von den restlichen Elementen (integer) der ersten list_t. Die Einschränkung besteht darin, dass diese Funktion und ggf. ihre Hilfsfunktionen tail-rekursiv sein müssen. Siehe den Prototyp für insert_list() hier:

/* 
* 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); 

Ich verbrachte Tage denken und Wege auszuprobieren diese angreifen, aber die am weitesten bekam ich würde umgekehrt die ersten n Zahlen haben. Ich habe eine Funktion geschrieben, die eine list_t umkehrt, aber ich wäre nicht in der Lage, einen Teil einer Liste umzukehren, nur eine ganze Liste umzukehren ist möglich und würde nicht in die Tail-Recursion-Struktur passen, die ich mir ausgedacht habe. Ich fragte mich auch, ob ich zwei rekursive Funktionen schreiben muss, die tatsächlich voneinander abhängen, aber auch keine brauchbare Lösung auf diesem Weg gefunden haben.

Answer 1

Sie müssen Elemente aus der ersten Liste hinzufügen und n dekrementieren, bis es Null erreicht. Dann müssen Sie Elemente aus der zweiten Liste hinzufügen, bis sie erschöpft sind, und schließlich den Rest der ersten Liste anhängen.

EDIT: die obige Beschreibung erreicht keine Tail-Rekursion. Ich habe die Implementierung dadurch modifiziert. Der Ansatz ist: während n über Null ist, nehmen Sie weiter Elemente von der Vorderseite first und predigen sie an second, während n dekrementieren. Wenn n Null erreicht, das Gegenteil tun: weiter Elemente von der Vorderseite second nehmen und sie vorläufig an first anhängen, bis second leer ist. Dies erreicht eine vollständige tail-rekursive Implementierung.

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