Fonction récursive

Tout d'abord, je voudrais résumer la fonction récursive car il existe de nombreuses possibilités d'utiliser la récurrence de la structure arborescente, comme une source arborescente, un algorithme d'arbre de décision, etc. La fonction qui s'exécute est appelée une fonction récursive, et la partie de la fonction récursive qui s'exécute est appelée un appel récursif.

recursive.ipynb


def recursive_f(depth):
  print("depth: "+ str(depth))
  if depth == 10:
    return 
  recursive_f(depth + 1)

if __name__=="__main__":
  recursive_f(0)

Le résultat de l'exécution est le suivant. depth: 0 depth: 1 depth: 2 depth: 3 depth: 4 depth: 5 depth: 6 depth: 7 depth: 8 depth: 9 depth: 10

Puisqu'il s'appelle lui-même, il continuera à s'exécuter indéfiniment à moins qu'une branche conditionnelle ne soit faite quelque part.

Lors de l'implémentation avec un arbre de décision, créez une classe de nœuds, ayez une variable membre pour stocker votre propre nœud enfant et créez une fonction membre qui vous divise et crée un nœud enfant en une fonction récursive. Une variable membre qui devient son propre nœud enfant a une variable membre qui devient un nœud petit-enfant, et a également une variable membre qui devient un nœud arrière-petit-enfant, et un nœud enfant est généré pour toujours comme. Par souci de simplicité, la figure lorsque la profondeur est de 3 est représentée. スクリーンショット 2020-01-21 15.26.30.png

Si vous codez ceci

recursive_tree.ipynb


class Node:
  def __init__(self, max_depth):
    self.left = None
    self.right = None
    self.max_depth = max_depth
    self.depth = None
        
  def split_node(self, depth):
      self.depth = depth
      print("depth: " + str(self.depth))
        
      if self.depth == self.max_depth:
          return

      self.left  = Node(self.max_depth)
      self.right = Node(self.max_depth)

      self.left.split_node(depth + 1)   # recursive call
      self.right.split_node(depth + 1)  # recursive call

if __name__ == "__main__":
    max_depth = 3
    initial_depth = 0

    tree = Node(max_depth)
    tree.split_node(initial_depth)

Résultat d'exécution depth: 0 depth: 1 depth: 2 depth: 3 depth: 3 depth: 2 depth: 3 depth: 3 depth: 1 depth: 2 depth: 3 depth: 3 depth: 2 depth: 3 depth: 3 Ce qui précède est un exemple d'utilisation d'une fonction récursive. Si vous apprenez cette idée, il sera plus facile d'implémenter l'algorithme d'arbre de décision, alors essayons-le.

Recommended Posts

Fonction récursive
fonction python ①
[Python] fonction
Zip récursif
Comment créer une fonction récursive
Fonction en fonction
fonction python ②
Examen des fonctions
python3x: fonction lambda
Python> fonction> Fermeture
[Python] Fonction de générateur
Dualité en fonction
Mémo de représentation récursive
Décorateur de fonction Python
Fonction récursive qui affiche l'arborescence XML [Note]
Comment résoudre la fonction récursive qui a résolu abc115-D
Envisagez la conversion de Python récursif en non récursif