递归函数通过调用自身将复杂问题分解为更小的子问题，直至达到基准条件。其核心包含基准条件和递归调用两部分，适用于树形结构遍历、分治算法、回溯问题及数学递推关系等场景，如阶乘、斐波那契数列和汉诺塔问题，能简洁表达自相似结构的求解过程，虽存在重复计算与栈溢出风险，但逻辑清晰且贴近问题本质。
递归函数是指在函数定义中调用自身的函数。它通过将一个复杂问题分解为相同类型的更小规模子问题来求解，直到达到一个可以直接解决的简单情况（称为“基准条件”或“终止条件”）。
递归的基本结构
一个有效的递归函数通常包含两个关键部分：
- 基准条件（Base Case）： 防止无限递归，是递归停止的条件。
- 递归调用（Recursive Call）： 函数调用自身，但传入更接近基准条件的参数。
例如：计算阶乘
阶乘 n! = n × (n-1) × ... × 1，可以用递归实现：
def factorial(n):
if n == 0 or n == 1: # 基准条件
return 1
return n * factorial(n - 1) # 递归调用
适合使用递归的场景
递归在处理具有自相似结构的问题时特别清晰和自然。以下是一些典型场景：
1. 树形结构的遍历
树的结构天然适合递归。比如遍历文件目录、解析DOM树、二叉树的前序/中序/后序遍历等。
每次访问一个节点后，递归处理其子节点，逻辑简洁明了。
2. 分治算法
像归并排序、快速排序这类算法，把数组分成两部分分别排序，再合并结果。递归能直观表达“先处理子问题，再整合”的思想。
3. 回溯问题
求解组合、排列、八皇后、数独等问题时，往往需要尝试所有可能路径，并在不满足条件时退回（回溯）。递归能自然地表达这种“试错 + 撤销”的过程。
4. 数学上的递推关系
斐波那契数列、汉诺塔等问题本身有明确的递推公式。用递归实现与数学定义几乎一致，代码易读。
例如汉诺塔：移动 n 层塔 = 移动上面 n-1 层 → 移动最底层 → 再移动 n-1 层，这个思路直接对应三行递归调用。
基本上就这些。递归不是总最优（可能有重复计算或栈溢出），但在结构匹配问题上，它让代码更贴近问题本质，减少人为控制的复杂性。只要注意设计好终止条件，递归是一种强大而优雅的编程工具。
