当前位置：首页 > java >正文

尾递归优化与函数柯里化

java 2025/7/6 3:23:52

本来只是查了一下尾递归，没想到又补充了新知识。都不是特别新颖的东西，作为学习记录一下。

尾递归

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生"栈溢出"错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。

function factorial(n) {if (n === 1) return 1;return n * factorial(n - 1);
}
factorial(5) // 120

上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用记录，复杂度 O(n) 。

如果改写成尾递归，只保留一个调用记录，复杂度 O(1) 。

function factorial(n, total) {if (n === 1) return total;return factorial(n - 1, n * total);
}factorial(5, 1) // 120

尾递归优化内存的原理

尾递归优化的核心在于编译器或解释器对尾递归函数的特殊处理。当检测到一个函数是尾递归时，编译器或解释器会将其转换为迭代形式，从而避免了栈帧的累积。在尾递归调用时，由于当前栈帧中的信息已经不再需要，所以可以直接将其替换为下一次递归调用的栈帧，从而实现了栈帧的重用。这样，无论递归深度有多大，栈的深度都不会增加，从而优化了内存占用。
需要注意的是，并非所有的编程语言都支持尾递归优化。Python 解释器就没有对尾递归进行优化，因此在 Python 中使用尾递归并不能减少内存占用。但在一些支持尾递归优化的语言中，如C++、 Scheme、Haskell 等，尾递归可以显著减少内存占用。

柯里化

因为上述递归函数，传入了两个参数，看起来有点”怪怪“的。最简单的改写形式是使用默认参数：

function factorial(n, total = 1) {if (n === 1) return total;return factorial(n - 1, n * total);
}factorial(5) // 120

另外就是复杂一些，柯里化——这是函数编程里面的概念：

function currying(fn, n) {return function (m) {return fn.call(this, m, n);};
}function tailFactorial(n, total) {if (n === 1) return total;return tailFactorial(n - 1, n * total);
}const factorial = currying(tailFactorial, 1);factorial(5) // 120

简单一点说，柯里化无非就是多了一层封装，把需要的参数或设定固定到函数里。

更深入的学习

回调函数定制
在 C++ 里，有时候需要注册回调函数，不过回调函数的参数可能会随着使用场景而变化。柯里化能帮你提前设定部分参数，从而生成定制化的回调函数。
```
#include <iostream>
#include <functional>// 一个通用的处理函数
void process(int a, int b, std::function<void(int)> callback) {int result = a + b;callback(result);
}// 柯里化函数，用于固定回调函数
std::function<std::function<void(int)>(int)> curry_callback(std::function<void(int)> callback) {return [callback](int a) {return [callback, a](int b) {process(a, b, callback);};};
}// 示例回调函数
void print_result(int result) {std::cout << "Result: " << result << std::endl;
}int main() {auto curried = curry_callback(print_result);auto with_a = curried(3);with_a(5);return 0;
}    
```
curry_callback 函数里嵌套了两个 lambda 表达式，柯里化后的函数需要3次调用才最终调用了实际处理的函数，第一次调用传入回调函数callback，此时返回外层lambda 表达式，相当于给外层lambda 表达式起了一个名字，第二次调用时需要传入一个int参数，调用完成后，返回内层lambda 表达式，并固定了外层lambda的参数a，第三次调用时同样传入一个int参数，传入参数后，再次调用process，实现最终的处理。

模板元编程
在模板元编程中，柯里化可用于分步处理模板参数。借助模板函数和模板类的特化，能够实现柯里化的效果。

#include <iostream>// 模板类实现柯里化
template <int A>
struct Adder {template <int B>struct Add {static constexpr int value = A + B;};
};int main() {constexpr int result = Adder<3>::Add<5>::value;std::cout << "Result: " << result << std::endl;return 0;
}

事件处理与信号系统
在事件处理和信号系统中，柯里化可用于创建带有特定上下文的事件处理函数。

#include <iostream>
#include <functional>
#include <vector>// 事件处理类
class EventHandler {
public:void register_event(std::function<void(int)> event) {events.push_back(event);}void trigger_events(int value) {for (auto& event : events) {event(value);}}private:std::vector<std::function<void(int)>> events;
};// 柯里化函数，用于创建带有特定上下文的事件处理函数
std::function<void(int)> curry_event(int context) {return [context](int value) {std::cout << "Context: " << context << ", Value: " << value << std::endl;};
}int main() {EventHandler handler;auto event1 = curry_event(1);auto event2 = curry_event(2);handler.register_event(event1);handler.register_event(event2);handler.trigger_events(10);return 0;
}