掌握Rust递归算法（从零开始学会用Rust实现递归）

Rust中如何写递归函数？

在Rust中，递归函数和其他函数一样，只是它会在函数体内调用自己。但要注意：必须设置终止条件（也叫基线条件），否则程序会无限递归，最终导致栈溢出。

示例1：用递归实现阶乘

阶乘是一个经典的递归例子。n! = n × (n-1)!，而0! = 1。

fn factorial(n: u32) -> u32 {    if n == 0 {        1    } else {        n * factorial(n - 1)    }}fn main() {    let result = factorial(5);    println!("5! = {}", result); // 输出：5! = 120}

这段代码展示了如何用Rust函数式编程风格编写一个简洁的递归函数。注意：我们使用了u32类型来避免负数输入（因为阶乘只对非负整数定义）。

示例2：斐波那契数列

斐波那契数列定义为：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

fn fibonacci(n: u32) -> u32 {    match n {        0 => 0,        1 => 1,        _ => fibonacci(n - 1) + fibonacci(n - 2),    }}fn main() {    println!("fibonacci(6) = {}", fibonacci(6)); // 输出：8}

⚠️ 注意：这个实现虽然简单，但效率很低（指数时间复杂度）。在实际项目中，建议使用动态规划或记忆化优化。但对于学习递归实现阶乘和理解递归思想非常有帮助。

递归的优缺点

• 优点：代码简洁、逻辑清晰，特别适合处理树形结构或分治问题。
• 缺点：可能导致栈溢出；某些情况下效率较低（如未优化的斐波那契）。

小贴士：避免栈溢出

Rust默认的栈大小有限。对于深度递归，可考虑改用迭代方式，或使用尾递归优化（虽然Rust目前不保证尾递归优化，但你可以手动改写为循环）。

总结

通过本教程，你已经学会了如何在Rust中编写基本的递归函数，并理解了其核心思想。无论是Rust递归算法还是Rust函数式编程，递归都是一个强大而优雅的工具。多加练习，你会越来越熟练！

希望这篇Rust初学者教程对你有帮助。动手试试修改上面的代码，比如计算10的阶乘，或者打印前10个斐波那契数吧！