So I am struggling with understanding recursion in the context of decision trees. I have looked at two different codes from two different websites: Example 1 and Example 2. This is a part of the code from the first example:
class DecisionTreeClassifier():
def __init__(self, min_samples_split=2, max_depth=2):
''' constructor '''
# initialize the root of the tree
self.root = None
# stopping conditions
self.min_samples_split = min_samples_split
self.max_depth = max_depth
def build_tree(self, dataset, curr_depth=0):
''' recursive function to build the tree '''
X, Y = dataset[:,:-1], dataset[:,-1]
num_samples, num_features = np.shape(X)
# split until stopping conditions are met
if num_samples>=self.min_samples_split and curr_depth<=self.max_depth:
# find the best split
best_split = self.get_best_split(dataset, num_samples, num_features)
# check if information gain is positive
if best_split["info_gain"]>0:
# recur left
left_subtree = self.build_tree(best_split["dataset_left"], curr_depth+1)
# recur right
right_subtree = self.build_tree(best_split["dataset_right"], curr_depth+1)
# return decision node
return Node(best_split["feature_index"], best_split["threshold"],
left_subtree, right_subtree, best_split["info_gain"])
# compute leaf node
leaf_value = self.calculate_leaf_value(Y)
# return leaf node
return Node(value=leaf_value)
I can't wrap my head around how the information about the split decisions and thresholds are "saved" while performing the recursion. In both of the codes they return only one node after the recursion is done, but how can this node store the whole tree, when it is only one node? Should not a tree be able to contain many nodes?
Since the recursion is performed before the making of the node, how is the information about the different split decisions and thresholds "stored" before making the node? This might be some stupid questions but I am really struggling with understanding this concept and was hoping if someone had a good explanation that could help me visualize what happens during the recursion.