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.
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