递归 = 把大问题拆成逻辑相同、规模更小的子问题，直到遇到终止条件，再逐层返回结果。 阶乘是它最经典的单链形态；决策树则是它最经典的多分支形态。
任何递归函数都必须同时具备这两块。缺了基线条件，程序会无限递归直到栈溢出；缺了递归调用，它就只是一个普通函数。
当问题已经小到可以直接给出答案，不再继续往下拆。
例如：0! = 1；决策树里"样本已全属同一类"。
把原问题交给和自己逻辑完全一样的子任务去处理，只是输入规模变小。
例如：n! = n × (n-1)!；决策树里"对每个子集继续建树"。
阶乘是入门递归的第一个例子：每次只产生一个子调用，调用栈是一条直线，最容易看清"递"和"归"。
0! = 1 （基线条件） | n! = n × (n-1)! （递归规则）
def fact(n): if n == 0: # 基线条件：到这里停止往下拆 return 1 return n * fact(n - 1) # 递归调用：规模减 1
递（往下拆，压栈）： fact(4) → 4 * fact(3) fact(3) → 3 * fact(2) fact(2) → 2 * fact(1) fact(1) → 1 * fact(0) fact(0) → return 1 ← 基线触发 归（往回返，弹栈）： fact(1) = 1 * 1 = 1 fact(2) = 2 * 1 = 2 fact(3) = 3 * 2 = 6 fact(4) = 4 * 6 = 24
fact(-1)，永远碰不到 n == 0，递归不会停止——这就是栈溢出。真实代码里要加输入保护。
决策树不是"算出一个数"，而是"长出一棵树"。每处理一个节点，它会把数据集拆成多个子集，再对每一个子集调用自己——这是和阶乘最大的不同。
def build_tree(D): # —— 基线条件：满足任意一条，就生成叶子节点，不再分裂 —— if D 中样本全属于同一类: return 叶子节点(该类别) if 没有剩余特征可用于划分: return 叶子节点(多数投票类别) # —— 递归步骤：选特征、切数据集 —— 选择最优划分特征 A # 信息增益 / 基尼系数 将 D 按 A 的取值切成子集 D₁, D₂, …, D_k # —— 多分支递归：每个子集都重新调用 build_tree —— for Di in [D₁, D₂, …, D_k]: 子节点 = build_tree(Di) # —— 归：所有子树都建好后，组装成当前内部节点 —— return 内部节点(A, [子节点₁, 子节点₂, …])
两者共享同一套递归骨架，差别只在"一次拆出几个子问题"和"返回值是什么"。
| 对比维度 | 阶乘（单链递归） | 决策树（多分支递归） |
|---|---|---|
| 一次拆出几个子问题 | 1 个：fact(n-1) | 多个：build_tree(D₁), build_tree(D₂), … |
| 返回值是什么 | 一个数字（运算结果） | 一个节点对象（叶子 / 内部节点） |
| "归"阶段做什么 | 把数字乘起来 | 把子节点挂到当前内部节点上 |
| 调用栈形态 | 一条直线（线性） | 一棵分叉的树 |
| 终止条件 | n == 0 | 样本纯 / 无特征可用 |
| 递归深度 | 等于 n 本身 | 等于树的深度（过拟合时过深） |
下面两个小工具可以让你单步观察调用栈的变化。点击"单步"按钮，看每一帧是怎么压栈、怎么回弹的。
西瓜例子（11 条样本，3 个特征：纹理 / 根蒂 / 敲声）。本例中三个特征都参与了分类： 根按纹理、清晰分支按根蒂、蜷缩分支再按敲声分裂。
| 编号 | 纹理 | 根蒂 | 敲声 | 好瓜？ |
|---|---|---|---|---|
| 1 | 模糊 | 蜷缩 | 浊响 | 坏 |
| 2 | 模糊 | 硬挺 | 沉闷 | 坏 |
| 3 | 模糊 | 蜷缩 | 沉闷 | 坏 |
| 4 | 清晰 | 硬挺 | 浊响 | 好 |
| 5 | 清晰 | 硬挺 | 沉闷 | 好 |
| 6 | 清晰 | 硬挺 | 浊响 | 好 |
| 7 | 清晰 | 蜷缩 | 浊响 | 坏 |
| 8 | 清晰 | 蜷缩 | 浊响 | 坏 |
| 9 | 清晰 | 蜷缩 | 沉闷 | 好 |
| 10 | 清晰 | 蜷缩 | 浊响 | 好 |
| 11 | 模糊 | 硬挺 | 浊响 | 坏 |
| 12 | 清晰 | 蜷缩 | 沉闷 | 好 |
统计：好瓜 6 条（4、5、6、9、10、12），坏瓜 6 条（1、2、3、7、8、11），好坏对半。根节点 Gini = 0.5； 经计算，根选纹理（模糊全坏直接成叶子），清晰分支选根蒂（硬挺全好成叶子），蜷缩分支再选敲声——三个特征各用一次。
def solve(problem): # 1. 先判终止 if 足够简单: return 直接答案 # 2. 拆子问题并递归 sub = 拆解(problem) result = solve(sub) # 3. 归：组装返回 return 结合(result)