波仔
🧩 附章 函数式语言是怎样工作的
📄 一句话概括

三个课题各一条硬证据：递归 1100 个元素就崩（上限 1000）、朴素 fib(12) 要多算 38 倍、入门要过 6 个概念——都是实打实的门槛，不是偏见。

📝 本节和前面几节的关系

A.12 讲优势，这一节讲代价——两边都看清，才算真认识。

一、实测三个课题

递归有上限：默认 1000 层，超一层直接抛 RecursionError。 纯函数会重复算：算 fib(12) 朴素递归调用 465 次，记忆化只需 12 次，差 38 倍。 概念门槛高：入门要过 6 个（纯函数／高阶／柯里化／模式匹配／类型／单子）。

二、三个课题各自的根

递归上限：来自栈——每层调用占一块栈帧，栈是有限的。 重复计算：来自【不能改东西】——不改就没法缓存中间结果，得自己加记忆化。 概念门槛：来自【必须把副作用隔出去】——单子就是那套隔法。

三、实际怎么绕

递归太深：换循环，或改用库里的迭代实现。 重复计算：加记忆化（functools.lru_cache 一行搞定）。 概念太绕：先只用推导式和纯函数，单子这些等真需要再学。

四、动手 Demo：函数式语言的课题

试探递归上限，量朴素递归与记忆化的调用次数。 两版结果必须一致。

import sys

def rsum(xs):
    if not xs:
        return 0
    return xs[0] + rsum(xs[1:])

try:
    rsum(list(range(sys.getrecursionlimit() + 50)))
except RecursionError:
    print("超限")                      # 超限

counter = {"n": 0}
def fib(n):
    counter["n"] += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(12)
print(counter["n"])                    # 465

实跑输出：

--------------------------------------------------------------------
函数式语言的课题
--------------------------------------------------------------------

  三个课题各给一条硬证据：

      ① 递归深度：默认上限 1000 层，超一层就抛 RecursionError = True
      ② 性能：算 fib(12) 朴素版调用了 465 次，记忆化版只需 12 次
      ③ 学习曲线：入门要过的概念 6 个（纯函数／高阶／柯里化／模式匹配／类型／单子）

      两版 fib(12) 结果一致       True
      朴素版比记忆化多算        38 倍

  **课题一：递归不是免费的**——**深度有上限，超了就崩，这是能不能跑的问题。**
  **课题二：纯函数会重复算**——**不改东西就没法缓存，得自己加记忆化。**
  **课题三：概念门槛高**——**单子这类东西，是很多人放弃的地方。**

实测：递归超 1000 层直接抛 RecursionError；朴素 fib(12) 调用 465 次，记忆化只需 12 次。 三个课题各有根：栈有限、不能改所以没法缓存、副作用隔离带来概念门槛。 实际都能绕：换循环、加 lru_cache、先不碰单子。

30 秒实验

  1. 给一段递归函数加 functools.lru_cache，看调用次数降到多少。
  2. 再把一段深递归改成循环，看深度限制是不是消失了。

常见误区

  1. 以为递归优雅就可以随便用。深度是硬限制，跟优雅无关。
  2. 一上手就学单子。先把推导式和纯函数用熟，收益大得多。
自测三问（点开对答案） 1. 递归上限是多少？超了会怎样？ —— 默认 1000 层，超了抛 RecursionError。 2. 朴素 fib(12) 调用多少次？ —— 465 次；记忆化只需 12 次，差 38 倍。 3. 三个课题怎么绕？ —— 深递归换循环、重复算加 lru_cache、概念门槛先只用推导式和纯函数。

相关笔记