Recursion Question: Révision

Question

Mes diapositives disent que:

• Un appel récursif devrait toujours être sur une plus petite structure de données que celle

• actuelle Il doit y avoir une option non récurrente si la structure de données est trop petite

• Vous avez besoin d'une méthode d'emballage pour rendre la méthode récursive accessible

Il est insensé de lire ceci dans les diapositives, surtout que c'était un sujet d'avant Noël!

Quelqu'un pourrait-il essayer de clarifier ce que cela signifie s'il vous plaît?

Merci

Answer 1

Un appel recurssive devrait toujours être sur une plus petite structure de données que celle

courant En général, ce n'est pas vrai, mais si vous parlez de listes chaînées manipulation avec récursivité c'est. Ce que cela implique, c'est que vous devez toujours travailler vers une solution et cela traite généralement un problème plus petit que vous avez commencé avec.

Prenons par exemple le port de réponse rapide. Chaque fois que la fonction est appelée, elle fonctionne avec un ensemble de données plus petit. Pour prendre un autre exemple d'impression d'une liste chaînée, la prochaine fois que vous appelez la fonction récursive, l'argument doit être la queue de la liste chaînée (ce code comporte une erreur, mais cela nous amène au point suivant)

void printList(List l){ 
    print(l.head); 
    printList(l.tail); 
} 

Il doit y avoir une option non recurssive si la structure de données est trop petite

Cela signifie qu'il devrait y avoir un cas de base. Le point où la fonction cesse de s'appeler à nouveau.

int factorial(int n){ 
    if (n == 1){ //the base case is when n = 1 
     return 1; 
    } 
    return n*factorial(n-1); 
} 

Pour en revenir à l'exemple d'imprimer une liste chaînée, il doit y avoir un cas où vous avez seulement une liste vide à gauche (dans ce cas, la fonction ne doit rien faire). Pour en revenir au code d'imprimer une liste chaînée

void printList(List l){ 
    if (l.empty == true){ //the base case is when the list l is empty 
     return; 
    } 

    print(l.head); 
    printList(l.tail); 
} 

Vous avez besoin d'une méthode d'emballage pour rendre la méthode recurssive accessible

Je ne sais pas Java, et il est pas vraiment langage conçu pour la récursivité, mais dans de nombreux cas, votre fonction récursive aura plus de paramètres que la personne qui utilise l'API devrait être en mesure de voir. Vous pourriez par exemple vouloir avoir un compteur là-dedans.

Vous pouvez avoir une fonction d'encapsulation qui simplifie les paramètres juste ce dont vous avez besoin. La fonction wrapper appelle ensuite la fonction de vrai worker.

Un exemple pourrait être si nous avons une classe de liste liée qui a la fonction récursive pour imprimer la liste. Sa déclaration ressemblerait à quelque chose comme ceci:

void printList(List l); 

Cependant, comme il est une méthode de classe, à une personne qui utilise l'API, il ne fait pas grand-chose sence d'avoir à faire:

myList.printList(myList); 

Ainsi, une La fonction wrapper peut être créée sans paramètre qui appelle ensuite le code qui fait le travail.

void printList(){ 
    doPrintList(this); //pass in the List object as the first argument 
} 

Ensuite, tout le programmeur en utilisant l'API doit faire est:

myList.printList();