Rust专项——算法专项：斐波那契数列——递归实现与优化

红目香薰

发布于 2025-12-16 16:35:53

160

斐波那契数列是经典的递归算法案例，也是理解递归思想、性能优化与 Rust 内存管理的最佳入门示例。本文将系统讲解斐波那契数列的递归实现，分析性能瓶颈，并给出多种优化方案。

注：引入的内容：

[package]
name = "my_library"
version = "0.1.0"
edition = "2021"
[dependencies]
tokio = { version = "1", features = ["full"] }
anyhow = "1.0"
num-bigint = "0.4"
num-traits = "0.2"

1. 斐波那契数列定义

斐波那契数列（Fibonacci Sequence）的数学定义：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)

前几项：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

2. 基础递归实现

2.1 朴素递归版本

fn fibonacci(n: u32) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

fn main() {
    for i in 0..10 {
        println!("F({}) = {}", i, fibonacci(i));
    }
    
    // 性能测试：计算 F(40)
    let start = std::time::Instant::now();
    let result = fibonacci(40);
    let duration = start.elapsed();
    println!("F(40) = {}, 耗时: {:?}", result, duration);
    // 输出：耗时可能达到数秒，效率极低！
}

问题分析：

时间复杂度：O(2^n) - 指数级增长
空间复杂度：O(n) - 递归调用栈深度
重复计算：fibonacci(5) 会重复计算 fibonacci(3)、fibonacci(2) 等多次

3. 优化方案一：记忆化（Memoization）

使用 HashMap 缓存已计算结果，避免重复计算：

use std::collections::HashMap;

fn fibonacci_memo(n: u32, memo: &mut HashMap<u32, u64>) -> u64 {
    // 先查缓存
    if let Some(&val) = memo.get(&n) {
        return val;
    }
    
    // 基础情况
    let result = match n {
        0 => 0,
        1 => 1,
        _ => {
            fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
        },
    };
    
    // 存入缓存
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    let start = std::time::Instant::now();
    let result = fibonacci_memo(40, &mut memo);
    let duration = start.elapsed();
    println!("F(40) = {}, 耗时: {:?}", result, duration);
    // 输出：耗时通常 < 1ms，大幅提升！
}

性能提升：

时间复杂度：O(n) - 每个值只计算一次
空间复杂度：O(n) - 存储 n 个结果

4. 优化方案二：迭代（动态规划）

从下往上计算，避免递归调用栈：

fn fibonacci_iter(n: u32) -> u64 {
    if n == 0 {
        return 0;
    }
    if n == 1 {
        return 1;
    }
    
    let mut prev = 0u64;
    let mut curr = 1u64;
    
    for _ in 2..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }
    
    curr
}

fn main() {
    let start = std::time::Instant::now();
    let result = fibonacci_iter(40);
    let duration = start.elapsed();
    println!("F(40) = {}, 耗时: {:?}", result, duration);
    // 输出：耗时 < 1μs，最优性能！
}

性能优势：

时间复杂度：O(n) - 线性时间
空间复杂度：O(1) - 只使用两个变量
无递归开销：无函数调用栈，最快

5. 优化方案三：矩阵快速幂（高级算法）

利用矩阵乘法快速计算，时间复杂度 O(log n)：

use num_bigint::BigUint;
use num_traits::{One, Zero};
use std::time::Instant;

// 移除 Copy 派生，保留 Clone（BigUint 实现了 Clone）
#[derive(Debug, Clone)] 
struct Matrix2x2 {
    a: BigUint,
    b: BigUint,
    c: BigUint,
    d: BigUint,
}

impl Matrix2x2 {
    fn multiply(&self, other: &Matrix2x2) -> Matrix2x2 {
        Matrix2x2 {
            a: &self.a * &other.a + &self.b * &other.c,
            b: &self.a * &other.b + &self.b * &other.d,
            c: &self.c * &other.a + &self.d * &other.c,
            d: &self.c * &other.b + &self.d * &other.d,
        }
    }
    
    fn power(&self, n: u32) -> Matrix2x2 {
        if n == 0 {
            Matrix2x2 { 
                a: BigUint::one(), 
                b: BigUint::zero(), 
                c: BigUint::zero(), 
                d: BigUint::one(),
            }
        } else if n % 2 == 0 {
            let half = self.power(n / 2);
            half.multiply(&half)
        } else {
            self.multiply(&self.power(n - 1))
        }
    }
}

fn fibonacci_matrix(n: u32) -> BigUint {
    if n == 0 {
        return BigUint::zero();
    }
    let base = Matrix2x2 { 
        a: BigUint::one(), 
        b: BigUint::one(), 
        c: BigUint::one(), 
        d: BigUint::zero(), 
    };
    let result = base.power(n - 1);
    result.a
}

fn main() {
    let start = Instant::now();
    let result = fibonacci_matrix(1000); 
    let duration = start.elapsed();
    println!("F(1000) = {}", result);
    println!("耗时: {:?}", duration);
}

适用场景：

时间复杂度：O(log n) - 对数时间，适合超大 n
空间复杂度：O(log n) - 递归栈深度

6. 性能对比表

方法	时间复杂度	空间复杂度	F(40) 耗时	适用场景
朴素递归	O(2^n)	O(n)	~数秒	教学演示
记忆化递归	O(n)	O(n)	~1ms	中等规模，需要递归思维
迭代（DP）	O(n)	O(1)	~1μs	推荐：简单高效
矩阵快速幂	O(log n)	O(log n)	~1μs	超大 n（如 n > 10^9）

7. Rust 特有优化：使用 `Vec` 预分配记忆化

fn fibonacci_vec(n: u32) -> u64 {
    let mut memo = vec![0u64; (n + 1) as usize];
    memo[0] = 0;
    if n > 0 {
        memo[1] = 1;
    }
    
    for i in 2..=n {
        memo[i as usize] = memo[(i - 1) as usize] + memo[(i - 2) as usize];
    }
    
    memo[n as usize]
}

优势：

Vec 连续内存，访问更快
预分配容量，无 HashMap 哈希开销
适合计算序列中的多个值

8. 生成斐波那契数列（迭代器风格）

使用 Rust 迭代器生成无限序列：

struct Fibonacci {
    prev: u64,
    curr: u64,
}

impl Iterator for Fibonacci {
    type Item = u64;
    
    fn next(&mut self) -> Option<Self::Item> {
        let next = self.prev + self.curr;
        self.prev = self.curr;
        self.curr = next;
        Some(self.prev)
    }
}

fn fibonacci_seq() -> Fibonacci {
    Fibonacci { prev: 0, curr: 1 }
}

fn main() {
    // 生成前10个斐波那契数
    for (i, val) in fibonacci_seq().take(10).enumerate() {
        println!("F({}) = {}", i, val);
    }
    
    // 查找第一个大于1000的数
    if let Some((i, val)) = fibonacci_seq().enumerate().find(|(_, v)| *v > 1000) {
        println!("F({}) = {} > 1000", i, val);
    }
}

9. 常见错误与修复

错误1：溢出

// ❌ 错误：u32 在 F(47) 附近溢出
fn fibonacci(n: u32) -> u32 { /* ... */ }

// ✅ 修复：使用 u64 或 BigInt
fn fibonacci(n: u32) -> u64 { /* ... */ }

错误2：负数输入

// ❌ 错误：未处理负数
fn fibonacci(n: i32) -> u64 { /* ... */ }

// ✅ 修复：类型约束或检查
fn fibonacci(n: u32) -> u64 { /* ... */ }
// 或
fn fibonacci_safe(n: i32) -> Option<u64> {
    if n < 0 { return None; }
    Some(fibonacci(n as u32))
}

错误3：记忆化未传递引用

// ❌ 错误：每次递归都创建新的 HashMap
fn fibonacci_memo(n: u32, memo: HashMap<u32, u64>) -> u64 { /* ... */ }

// ✅ 修复：使用可变引用
fn fibonacci_memo(n: u32, memo: &mut HashMap<u32, u64>) -> u64 { /* ... */ }

10. 实战练习

实现记忆化版本：使用 HashMap 优化递归版本，对比性能提升。
实现迭代版本：从下往上计算，要求空间复杂度 O(1)。
生成序列：实现 fibonacci_iter() 迭代器，生成前 n 个斐波那契数。
查找特定值：找出第一个大于 1000000 的斐波那契数及其索引。
对比性能：编写基准测试，对比四种方法的性能差异（可使用 criterion）。

11. 扩展：其他递归算法对比

11.1 阶乘（Factorial）

// 递归版本
fn factorial(n: u32) -> u64 {
    if n <= 1 {
        1
    } else {
        n as u64 * factorial(n - 1)
    }
}

// 迭代版本
fn factorial_iter(n: u32) -> u64 {
    (1..=n).product()
}

11.2 汉诺塔（Tower of Hanoi）

fn hanoi(n: u32, from: &str, to: &str, aux: &str) {
    if n == 1 {
        println!("移动盘子从 {} 到 {}", from, to);
    } else {
        hanoi(n - 1, from, aux, to);
        println!("移动盘子从 {} 到 {}", from, to);
        hanoi(n - 1, aux, to, from);
    }
}

12. 总结

核心要点

递归思想：将问题分解为更小的子问题
性能问题：朴素递归存在大量重复计算
优化策略：记忆化、迭代、矩阵快速幂
Rust 特性：利用所有权、借用、迭代器写出高效代码

选择建议

教学/理解递归：朴素递归
实际应用（n < 100）：迭代版本（最简单高效）
超大 n（n > 10^9）：矩阵快速幂
需要生成序列：迭代器实现

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-16，如有侵权请联系 cloudcommunity@tencent.com 删除

递归

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

Rust专项——算法专项：斐波那契数列——递归实现与优化

Rust专项——算法专项：斐波那契数列——递归实现与优化

1. 斐波那契数列定义

2. 基础递归实现

2.1 朴素递归版本

3. 优化方案一：记忆化（Memoization）

4. 优化方案二：迭代（动态规划）

5. 优化方案三：矩阵快速幂（高级算法）

6. 性能对比表

7. Rust 特有优化：使用 `Vec` 预分配记忆化

8. 生成斐波那契数列（迭代器风格）

9. 常见错误与修复

错误1：溢出

错误2：负数输入

错误3：记忆化未传递引用

10. 实战练习

11. 扩展：其他递归算法对比

11.1 阶乘（Factorial）

11.2 汉诺塔（Tower of Hanoi）

12. 总结

核心要点

选择建议

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

Rust专项——算法专项：斐波那契数列——递归实现与优化

Rust专项——算法专项：斐波那契数列——递归实现与优化

1. 斐波那契数列定义

2. 基础递归实现

2.1 朴素递归版本

3. 优化方案一：记忆化（Memoization）

4. 优化方案二：迭代（动态规划）

5. 优化方案三：矩阵快速幂（高级算法）

6. 性能对比表

7. Rust 特有优化：使用 Vec 预分配记忆化

8. 生成斐波那契数列（迭代器风格）

9. 常见错误与修复

错误1：溢出

错误2：负数输入

错误3：记忆化未传递引用

10. 实战练习

11. 扩展：其他递归算法对比

11.1 阶乘（Factorial）

11.2 汉诺塔（Tower of Hanoi）

12. 总结

核心要点

选择建议

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

7. Rust 特有优化：使用 `Vec` 预分配记忆化