[PYTHON] Recursive function

First, I would like to summarize the recursion function because I often use tree sources, decision tree algorithms, and tree-structured recursion. A function that executes itself is called a recursive function, and the part of the recursive function that executes itself is called a recursive call.

recursive.ipynb


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

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

The execution result is as follows. depth: 0 depth: 1 depth: 2 depth: 3 depth: 4 depth: 5 depth: 6 depth: 7 depth: 8 depth: 9 depth: 10

Since it calls itself, execution will continue indefinitely unless a conditional branch is made somewhere.

When implementing with a decision tree, you can create a node class, have a member variable to store your own child node, and make a member function that divides you and creates a child node into a recursive function. A member variable that becomes its own child node has a member variable that becomes a grandchild node, and a member variable that becomes a great-grandchild node, and a child node is generated forever, such as. For the sake of simplicity, the figure when the depth is 3 is shown. スクリーンショット 2020-01-21 15.26.30.png

If you code this

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)

Execution result 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 The above is an example of using a recursive function. If you learn this idea, the decision tree algorithm will be easier to implement, so give it a try.

Recommended Posts

Recursive function
python function ①
[Python] function
Recursive zip
How to make a recursive function
In-function function
python function ②
Function review
python3x: lambda function
Python> function> Closure
[Python] Generator function
Duality in function
Recursive expression memo
Python function decorator
Recursive function that displays the XML tree structure [Note]
How to solve the recursive function that solved abc115-D
Consider a conversion from a Python recursive function to a non-recursive function