LinkedLists dans la récursivité python

Question

J'ai une implémentation simple de LinkedList en python. Comment utiliser récursion dans une méthode? Je sais comment fonctionne la récursivité, mais comment utiliser moi-même avec la récursivité. Ce serait bien si quelqu'un peut corriger mon code mais je suis plus intéressé par l'explication afin que je puisse l'utiliser dans différentes méthodes.

Code LinkedList:

class Node: 
    def __init__(self, item, next): 
     self.item = item 
     self.next = next 

class LinkedList: 
    def __init__(self): 
     self.head = None 

    def add(self, item): 
     self.head = Node(item, self.head) 

    def remove(self): 
     if self.is_empty(): 
      return None 
     else: 
      item = self.head.item 
      self.head = self.head.next 
      return item 

    def is_empty(self): 
     return self.head == None 

Mon code est:

def count(self, ptr=self.head): 
    if ptr == None: 
     return '0' 
    else: 
     return 1 + self.count(ptr.next) 

Il me donne une erreur:

def count(self, ptr=self.head): 
NameError: name 'self' is not defined 

Toute aide est très appréciée.

Answer 1

En Python arguments par défaut sont pas expressions qui sont évaluées lors de l'exécution. Ce sont des expressions qui sont évaluées lorsque le def lui-même est évalué. Donc, pour un class habituellement lorsque le fichier est lu pour la première fois. Par conséquent, à ce moment-là, il n'y a pas de self. self est un paramètre. Donc, ce n'est disponible que lorsque vous appelez la fonction.

Vous pouvez résoudre ce problème en utilisant par exemple None par défaut et effectuer une vérification. Mais ici, nous ne pouvons pas utiliser None, puisque vous y avez déjà attaché une signification particulière. Nous pouvons cependant construire un objet dummy, et utiliser celui-ci:

dummy = object() 

def count(self, ptr=dummy): 
    if ptr is dummy: ptr = self.head 
    if ptr == None: 
     return '0' 
    else: 
     return 1 + self.count(ptr.next)

Un autre problème avec votre code est que vous renvoyer une chaîne zéro. Puisque vous ne pouvez pas simplement ajouter un entier et une chaîne, cela provoquera une erreur. Donc, vous devez retourner un entier à la place:

dummy = object() 

def count(self, ptr=dummy): 
    if ptr is dummy: 
     ptr = self.head 
    if ptr == None: 
     return 0 # use an integer 
    else: 
     return 1 + self.count(ptr.next)

Answer 2

Vous pouvez également mettre l'appel purement récursif dans une méthode spécifique, et d'utiliser un emballage autour:

def count(self): 
    def count_rec(ptr): 
     if ptr == None: 
      return 0 
     else: 
      return 1 + count_rec(ptr.next) 
    return count_rec(self.head) 

OMI, c'est plus propre que d'utiliser un un objet fictif et/ou des paramètres par défaut (btw, spécifier un paramètre par défaut dans une fonction récursive est souvent un bon signe que vous devriez considérer une fonction récursive interne et l'appeler de votre méthode avec l'initialisation correcte).