24、递归与数学：快速幂算法的递归实现

快速幂，这个名字听起来挺唬人的。其实说白了，就是教你如何高效地计算 a 的 n 次方。

你可能会想：「这有什么难的？一个 for 循环不就搞定了？」没错，如果 n 是 10、100，甚至 1000，循环确实没问题。但假如 n 是 10 亿呢？或者你的程序需要在嵌入式芯片上每秒算几千次幂运算？这时候，O(n) 的循环就扛不住了。

我在做网络协议栈的时候，遇到过加密模块的性能瓶颈。当时用的就是快速幂，把指数运算从 O(n) 降到了 O(log n)。嗯，这个提升可不是一星半点。

从暴力到优雅：为什么需要快速幂？

先看最朴素的写法：

// 暴力循环法
long long pow_naive(long long a, long long n) {
    long long result = 1;
    for (long long i = 0; i < n; i++) {
        result *= a;
    }
    return result;
}

这个函数，n 次乘法，时间复杂度 O(n)。当 n = 10^9 时，你的程序基本就卡死了。

那快速幂是怎么做的？它利用了指数的一个基本性质：

• 如果 n 是偶数：a^n = (a^(n/2))^2
• 如果 n 是奇数：a^n = a * a^(n-1)

你看，每次都能把指数砍掉一半。这就是 O(log n) 的来源。

递归实现：最直观的写法

我个人习惯先写递归版本，因为它最贴近数学定义，逻辑清晰，不容易出错。

// 递归实现快速幂
long long fast_pow_recursive(long long a, long long n) {
    // 基础情况：任何数的 0 次方等于 1
    if (n == 0) {
        return 1;
    }
    
    // 奇数情况
    if (n % 2 == 1) {
        return a * fast_pow_recursive(a, n - 1);
    }
    
    // 偶数情况
    long long half = fast_pow_recursive(a, n / 2);
    return half * half;
}

这段代码，你仔细看：

• 递归终止条件：n == 0，返回 1
• 奇数：先算 a^(n-1)，再乘 a
• 偶数：先算 a^(n/2)，再平方

为什么偶数情况要先把结果存到 half 里？因为如果你写成 fast_pow_recursive(a, n/2) * fast_pow_recursive(a, n/2)，那就递归调用了两次，时间复杂度又变回 O(n) 了。嗯，这个坑我曾经踩过。

递归的调用过程：画图理解

我们算一下 2^10，看看递归是怎么展开的：

fast_pow_recursive(2, 10)
  → n=10 偶数
  → half = fast_pow_recursive(2, 5)
      → n=5 奇数
      → 2 * fast_pow_recursive(2, 4)
          → n=4 偶数
          → half = fast_pow_recursive(2, 2)
              → n=2 偶数
              → half = fast_pow_recursive(2, 1)
                  → n=1 奇数
                  → 2 * fast_pow_recursive(2, 0)
                      → n=0 返回 1
                  → 返回 2 * 1 = 2
              → 返回 2 * 2 = 4
          → 返回 4 * 4 = 16
      → 返回 2 * 16 = 32
  → 返回 32 * 32 = 1024

一共只做了 4 次乘法（不算递归返回时的乘法），而暴力法需要 10 次。当 n 越大，差距越明显。

知识体系图

下面这张图展示了快速幂在整个递归知识体系中的位置：

避坑指南：递归的代价

递归版本虽然优雅，但有一个问题：每次递归调用都会消耗栈空间。当 n 很大时（比如 10^6），递归深度可能达到 20 层左右，这还好。但如果你的指数是 10^9，递归深度也就 30 层，完全没问题。

真正的问题在于——我曾经在某个嵌入式项目中，递归深度只有 10 层，但栈空间只给了 1KB。结果呢？栈溢出了。所以，如果你在资源受限的环境下编程，递归版本可能不是最佳选择。

迭代版本：空间换时间

如果你对栈空间有顾虑，可以改成迭代版本。我个人建议：先理解递归版本，再掌握迭代版本。两者相辅相成。

// 迭代实现快速幂
long long fast_pow_iterative(long long a, long long n) {
    long long result = 1;
    long long base = a;
    
    while (n > 0) {
        // 如果当前位是 1，乘上 base
        if (n & 1) {
            result *= base;
        }
        // base 自乘，准备下一位
        base *= base;
        // n 右移一位
        n >>= 1;
    }
    
    return result;
}

这个版本没有递归调用，空间复杂度 O(1)。它利用了二进制的思想：把 n 写成二进制，每一位对应一个 base 的幂。比如 n = 10（二进制 1010），就是 a^8 * a^2。

你想想看，迭代版本其实就是把递归版本的「分治」过程，用循环模拟出来了。底层逻辑完全一样。

实战：大数取模

在实际项目中，我们很少直接算 a^n，因为结果会溢出。更常见的场景是计算 a^n mod m，也就是带模的快速幂。

// 带模的快速幂（递归版本）
long long mod_pow_recursive(long long a, long long n, long long m) {
    if (n == 0) {
        return 1 % m;
    }
    
    if (n % 2 == 1) {
        return (a * mod_pow_recursive(a, n - 1, m)) % m;
    }
    
    long long half = mod_pow_recursive(a, n / 2, m);
    return (half * half) % m;
}

这个函数在密码学、哈希计算中非常常见。我在做 RSA 算法实现时，核心就是靠这个函数。每次加密解密，都要算大数的模幂，没有快速幂，RSA 根本跑不起来。

性能对比：递归 vs 迭代

维度	递归版本	迭代版本
时间复杂度	O(log n)	O(log n)
空间复杂度	O(log n)（栈空间）	O(1)
代码可读性	高（贴近数学定义）	中（需要理解二进制）
适用场景	教学、原型开发、栈空间充足	嵌入式、高性能、栈空间受限

我个人建议：学习阶段先用递归版本，把逻辑理清楚。实际项目中，如果性能要求高或者环境受限，再换成迭代版本。两个版本都掌握，你才算真正理解了快速幂。

好了，快速幂的递归实现就讲到这里。记住一句话：递归不是目的，分治才是。快速幂只是分治思想在指数运算中的一个漂亮应用。