闭包递归 | blog of peter

闭包(lambda/匿名函数)递归调用自己，看似一句"在函数体里调自己"，实则暗藏一个根本难题：闭包没有名字，它怎么在自己的函数体里指代自己？ 普通函数能递归，是因为它有名字；而闭包的精髓恰恰是"匿名"。这个"自我引用"(self-reference)的矛盾，是几乎所有支持闭包的语言都要面对的经典问题。各语言给出的答案大相径庭–有的靠外部命名变量捕获，有的靠把自己当参数传进去，有的干脆引入不动点组合子。本文梳理 C/C++、Java、Go、Rust、Python 五种语言的闭包递归实现，以斐波那契为例贯穿始终。

问题的本质：匿名性与自我引用

闭包 = 函数代码 + 捕获的环境。递归的核心需求是：执行体里要有一个名字来指代"自己这个可调用实体"。普通函数天然满足–函数名就是这个名字。闭包一旦匿名，这个名字就消失了。

直接写通常不行：

1 2	`// 伪代码：闭包内引用自己 let fib = \|n\| { ... fib(n-1) ... } // fib 此时还没声明完，引用不到`

这是个"鸡生蛋"问题：要推导/构造 fib，得先看右侧闭包体；而闭包体里又引用了 fib，得先知道 fib 是什么。绝大多数语言的类型系统或初始化分析在此处卡壳。

绕开它的通用思路有三条：

命名引用法：把闭包绑定到一个外部变量，闭包内通过该变量名调用自己。前提是语言允许"前向引用"或"延迟名字查找"。
自传递法：把闭包作为参数传给自己，绕开命名问题（f(f, n-1)）。
不动点组合子：用高阶函数构造递归（Y/Z combinator），完全不依赖命名。

下面逐一对照各语言。

C：没有闭包，但函数指针可以自传递

C 既没有 lambda，也没有捕获环境的能力，严格意义上不存在"闭包"。但普通函数天然支持递归（函数有名字）：

1
2
3

int fib(int n) {
    return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

真正有意思的是：当手上只有一个函数指针、且函数体内看不到自己的名字时（比如函数指针表、回调注册），如何递归？答案正是自传递–把函数指针作为参数显式传进来：

typedef int (*rec_fn)(rec_fn, int);  // pointer to a function taking itself

int fib(rec_fn self, int n) {
    return n <= 1 ? n : self(self, n - 1) + self(self, n - 2);
}

int main(void) {
    printf("%d\n", fib(fib, 10));   // 55
}

由于 C 无捕获，闭包递归在此意义不大；但 self(self, ...) 这套自传递写法，是后文多种语言在没有名字时的共同退路。

C++：std::function 命名引用与自传递

C++11 起 lambda 是带捕获的闭包对象。递归的关键在于：闭包内要能引用到"自己"。

命名引用：必须用 std::function

#include <functional>

std::function<int(int)> fib = [&](int n) -> int {
    return n <= 1 ? n : fib(n - 1) + fib(n - 2);
};

这里 [&] 按引用捕获所有自动变量，包括 fib 本身。闭包内 fib(n-1) 走的是 std::function::operator()，转发回 lambda 自身。

关键：不能用 auto。auto fib = [&](int n){ ... fib ... } 会在类型推导时失败–右侧求值时 fib 尚未声明，闭包内找不到它。必须先以 std::function 显式声明类型，让 fib 作为变量先存在；引用捕获拿到的是它的地址，运行时调用时 fib 早已赋值。

代价是 std::function 的类型擦除带来一次间接调用与可能的堆分配。

自传递：C++14 泛型 lambda

auto fib = [](auto& self, int n) -> int {
    return n <= 1 ? n : self(self, n - 1) + self(self, n - 2);
};
fib(fib, 10);

把闭包自身作为引用参数传入。闭包类型仍是匿名的，但靠 auto& 参数推导，调用时显式 fib(fib, ...)。零开销，无类型擦除。

C++23 deducing this：最优雅的解法

auto fib = [](this auto& self, int n) -> int {
    return n <= 1 ? n : self(n - 1) + self(n - 2);
};
fib(10);   // no need to pass self manually

deducing this 让 lambda 显式获得一个 self 参数，编译器自动把闭包对象传进去。调用处 fib(10) 与普通函数无异，兼顾了零开销与可读性。这是 C++ 为递归 lambda 量身定制的特性。

Java：函数式接口命名引用

Java 的 lambda 同样是闭包，且捕获的局部变量必须 effectively final。递归沿用命名引用法：

1
2
3

import java.util.function.Function;

Function<Integer, Integer> fib = n -> n <= 1 ? n : fib.apply(n - 1) + fib.apply(n - 2);

fib 被赋值一次，是 effectively final，可被 lambda 捕获。闭包内 fib.apply(...) 的执行发生在调用时，那时 fib 早已绑定，故合法。

"鸡生蛋"在这里被 Java 的延迟执行化解：lambda 体内对 fib 的引用不会在构造时求值，编译器只要求 fib 在"被使用时"已明确赋值即可。

基本类型可用 IntUnaryOperator 避免装箱：

1	`IntUnaryOperator fib = n -> n <= 1 ? n : fib.applyAsInt(n - 1) + fib.applyAsInt(n - 2);`

自传递在 Java 里需要先定义一个接受自身的函数式接口，远不如命名引用顺手，实践中几乎不用。

Go：先 var 声明，后赋值

Go 把函数当作一等公民，匿名函数即闭包（按引用捕获外部变量）。闭包递归的惯用法是两步走：

var fib func(int) int   // 1. declare first (zero value nil)
fib = func(n int) int { // 2. assign the closure
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}
fmt.Println(fib(10))

var fib func(int) int 先把 fib 声明为函数类型变量（初值 nil），随后赋值一个闭包。闭包按引用捕获 fib 这个变量，运行时调用时它已指向闭包自身。

为什么不能 fib := func(n int) int { ... fib(n-1) ... }？因为短变量声明 := 的左值在右侧表达式求值之后才生效，闭包体内的 fib 找不到当前作用域的定义，要么报 undefined: fib，要么错误地引用外层。先 var 后赋值正是 Go 解决"前向引用"的官方姿势。

具名函数递归当然最自然（func fib(n int) int { ... }），上面这套只在确实需要闭包（捕获局部状态）时才用。

Rust：借用检查下的三道关卡

Rust 是这里最棘手的。闭包类型是编译器生成的匿名类型，写不出来；再加上所有权与借用检查，直接自引用有三道关卡：

类型推导循环：let fib = |n| { ... fib(n-1) ... } 中，要推导 fib 的类型得分析闭包体，而闭包体又调用 fib，循环依赖。编译器直接报 cannot find value fib in this scope–fib 在 let 完成前不存在。
命名引用受阻：即便用 Box<dyn Fn> 显式标注类型，闭包仍需捕获 fib 的引用，而 fib 在初始化前被借用，触碰 Rust 的"使用未初始化变量"规则。不像 C++ 的 std::function + [&] 那样轻松放行。
借用排他性：若闭包是 FnMut（需可变借用 self 以修改捕获状态），递归调用会再次可变借用 self，违反"一个可变借用或任意多个不可变借用"的排他规则。

方案一：自传递（推荐，零开销）

let fib = |fib: &dyn Fn(i32) -> i32, n: i32| -> i32 {
    if n <= 1 {
        n
    } else {
        fib(fib, n - 1) + fib(fib, n - 2)
    }
};
println!("{}", fib(&fib, 10));

把闭包作为 &dyn Fn 参数显式传入，调用处 fib(&fib, 10) 把自己传给自己。类型在参数签名中写死，推导不再循环；闭包对自身是不可变借用（Fn），不违反排他性。这是最常见、开销最小的写法。

方案二：具名函数（无捕获时最简单）

fn fib(n: i32) -> i32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

普通函数有名字，递归天然可行。代价是失去捕获外部环境的能力。Rust 的态度很明确：能用具名函数就别用递归闭包。

方案三：Rc + RefCell（命名引用 + 捕获，繁琐）

当既需要命名引用、又需要捕获（甚至可变）状态时，只能上内部可变性 + 引用计数，先占位再替换：

use std::cell::RefCell;
use std::rc::Rc;

let fib: Rc<RefCell<Box<dyn Fn(i32) -> i32>>> =
    Rc::new(RefCell::new(Box::new(|_| 0)));      // placeholder
{
    let fib = Rc::clone(&fib);
    *fib.borrow_mut() = Box::new(move |n: i32| {  // swap in the real closure
        if n <= 1 {
            n
        } else {
            fib.borrow()(n - 1) + fib.borrow()(n - 2)
        }
    });
}
println!("{}", fib.borrow()(10));

RefCell 提供运行期可变借用以实现"先占位后替换"，Rc 让闭包能克隆一份自身引用进捕获环境。能用，但笨重–这是 Rust 为安全付出的代价。

Python：名字查找与不动点组合子

Python 变量是贴在对象上的名字标签，名字查找遵循 LEGB 规则（Local → Enclosing → Global → Builtin），且在运行时才解析。这让闭包递归格外灵活。

def 命名函数：最自然

1 2	`def fib(n): return n if n <= 1 else fib(n - 1) + fib(n - 2)`

fib 是名字，函数体运行时按名字查找，天然递归。

lambda + 名字引用

1	`fib = lambda n: n if n <= 1 else fib(n - 1) + fib(n - 2)`

lambda 引用的 fib 是赋值语句的左值，但闭包内对 fib 的访问在调用时才查名字表，那时 fib 已绑定，故可行。

注意按名字查找的副作用：若之后 fib 被重绑定，原 lambda 调用会用到新的 fib；若 del fib，再调用则 NameError。这与 Java/Rust 的"捕获值/引用"语义不同–Python 捕获的是名字，不是绑定。

不动点组合子（Z combinator）

完全不依赖命名，用高阶函数构造递归：

1
2
3

Z = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))
fib = Z(lambda f: lambda n: n if n <= 1 else f(n - 1) + f(n - 2))
print(fib(10))   # 55

Python 是按值调用（参数先求值），经典的 Y combinator（λf.(λx.f(x x))(λx.f(x x))）会因 x x 立即求值而无限递归。因此改用 Z combinator，用 lambda v: x(x)(v) 做 η-展开延迟求值。这是函数式编程的"原教旨"解法，工程上几乎不用，但能精确定义何为递归。

横向对比：三种解法的可用性

语言	命名引用法	自传递法	不动点组合子	直接 `let f = \|..\|{..f..}`
C	函数名即可	函数指针 `self(self,...)`	不常用	无闭包
C++	`std::function` + `[&]`（忌 `auto`）	泛型 lambda `self(self,...)`	可写	❌ 类型推导失败
Java	`Function` / `IntUnaryOperator`	需自定义接口，不实用	可写，繁琐	❌（需显式类型）
Go	`var` 先声明后赋值	可用	不常用	❌ `undefined: fib`
Rust	需 `Rc<RefCell<..>>`，繁琐	`&dyn Fn` 自传递，推荐	可写，繁琐	❌ 找不到 `fib`
Python	`fib = lambda ...` 名字查找	可用	Z combinator 经典	✅ 名字延迟查找

总结

闭包递归的本质，是"匿名实体如何自我引用"这一矛盾。各语言的解法折射出其类型系统与求值策略的取向：

C/C++ 把控制权交给程序员：C 靠函数名 + 自传递的函数指针；C++ 用 std::function 命名引用（忌 auto），泛型 lambda 自传递，C++23 deducing this 一锤定音。
Java 以函数式接口承载 lambda，命名引用靠 effectively final + 延迟执行化解前向引用。
Go 坚持"先 var 声明后赋值"，用闭包按引用捕获变量绕过 := 的作用域时序。
Rust 受匿名类型与借用排他性双重约束，推荐 &dyn Fn 自传递，否则退回具名函数或笨重的 Rc<RefCell<>>。
Python 借运行期名字查找，fib = lambda ... 直接可行，更有 Z combinator 的理论优雅。

三条解法–命名引用、自传递、不动点组合子–贯穿所有语言。理解了"名字从哪来"这一点，跨语言的闭包递归就不再神秘：差异只在于每种语言愿意为"前向引用"开多大的口子。