循环内双递归工作原理解析：圆上2n点无相交弦计数问题

嘿，这个问题其实就是经典的卡特兰数应用场景！我来一步步给你拆解清楚——从递归逻辑的核心，到递归树里两个递归调用的工作机制，再到可运行的代码，包你明白。

圆上2n个点绘制互不相交弦的方式数，正好等于第n个卡特兰数。比如：

• n=1（2个点）：1种方式
• n=2（4个点）：2种方式
• n=3（6个点）：5种方式
• n=4（8个点）：14种方式

我们可以用分治的思想拆解问题：

1. 固定任意一个点（比如第一个点，记为点0），它只能和奇数位置的点连弦（比如点1、3、...、2n-1）——这样连完后，弦会把圆分成两个独立的“子圆”，每个子圆内的点数都是偶数，才能继续生成互不相交的弦。
2. 假设点0和点2k+1连弦，那么左边子圆有2k个点（对应k对点），右边子圆有2(n-1-k)个点（对应n-1-k对点）。
3. 这两个子圆的互不相交弦方式数是相互独立的，所以当前连弦方案的总方式数是左边子问题的解 × 右边子问题的解。
4. 遍历所有合法的连弦选择，把所有情况的方式数相加，就是最终的答案。

对应的递归公式为：
f(n) = sum_{k=0到n-1} f(k) * f(n-1-k)
其中f(0)=1（0个点时，定义为1种“空方案”），f(1)=1。

咱们拿n=3（6个点）来举例，用文本递归树可视化两个递归的工作机制：

f(3)  # 6个点的总方案数
├── f(0) * f(2)  # 点0连点1：左边0个点，右边4个点
│   ├── f(0) * f(1)  # f(2)的第一个分支：点2连点3，左边0个点，右边2个点
│   │   └── f(0)*f(0)  # f(1)的唯一分支：一对点的方案
│   └── f(1) * f(0)  # f(2)的第二个分支：点2连点5，左边2个点，右边0个点
│       └── f(0)*f(0)
├── f(1) * f(1)  # 点0连点3：左边2个点，右边2个点
│   ├── f(0)*f(0)  # 左边子问题的解
│   └── f(0)*f(0)  # 右边子问题的解
└── f(2) * f(0)  # 点0连点5：左边4个点，右边0个点
    ├── f(0) * f(1)
    │   └── f(0)*f(0)
    └── f(1) * f(0)
        └── f(0)*f(0)

循环里的两个递归调用分工明确：

• 第一个递归f(k)：计算左边子圆（2k个点）的互不相交弦方式数
• 第二个递归f(n-1-k)：计算右边子圆（2(n-1-k)个点）的互不相交弦方式数

两者相乘代表当前连弦选择下的总方案数，循环遍历所有合法的连弦选择后累加，就得到了父问题的解。

基础递归版本 #

def count_non_intersecting_chords(n):
    # 边界条件：0个点时有一种空方案
    if n == 0:
        return 1
    total = 0
    # 遍历所有合法的连弦选择，计算子问题的乘积并累加
    for k in range(n):
        total += count_non_intersecting_chords(k) * count_non_intersecting_chords(n - 1 - k)
    return total

# 测试用例
print(count_non_intersecting_chords(1))  # 输出1
print(count_non_intersecting_chords(2))  # 输出2
print(count_non_intersecting_chords(3))  # 输出5
print(count_non_intersecting_chords(4))  # 输出14

记忆化优化版本（避免重复计算） #

基础递归会重复计算大量子问题，用缓存优化后效率大幅提升：

from functools import lru_cache

@lru_cache(maxsize=None)
def count_non_intersecting_chords(n):
    if n == 0:
        return 1
    total = 0
    for k in range(n):
        total += count_non_intersecting_chords(k) * count_non_intersecting_chords(n - 1 - k)
    return total

内容的提问来源于stack exchange，提问作者WRICK