提问：为什么它们都叫函数？

计算机里的 “函数”

int main() {
    for (int i = 0; i < 100; i++) {
        cout << i << endl;
    }
}

数学里的 “函数”

• • 似乎 C++ 函数比数学里的函数多了一些什么
  • 但又说不清多了什么？

改变一个思路

如果我们不允许你在函数里引入副作用

• 禁止引用任何全局变量 (可以引用常量)
• 禁止调用任何有全局影响的外部函数
  • 禁止：cout
  • 允许：sort
• 两种 “函数” 就很像了
  • vector, string, map 也都是 “数字”

有一个名字：“pure function” (纯函数)

• 来自 “函数式编程”，行为类似数学上的函数：无论调用多少次，结果都是一样的

递归函数

自己可以引用自己的函数

• • 数学课：从边界出发，推出很多
  • 计算机课：从 开始展开，直到遇到边界

C++ 也支持这样的表达 (fibonacci.cc)

int f(int n) {
    if (n <= 1) return n;
    return f(n - 1) + f(n - 2);
}

递归函数

计算机的函数允许一切 “复合数字”

• string, vector, map, ...
• 只要递归总是回到边界即可

例子：

string f(int n) {
    if (n == 0) return "a";
    if (n == 1) return "b";
    return f(n - 1) + f(n - 2);
}

递归函数

参数也可以是多个数字，或者 “复合数字”

• 无论有多少参数，函数就是实现 “对象到对象的转换”

给定一个集合 ，生成它所有的子集

• 如果 ，
• 否则 ，
  • 这是完全 “数学” 的定义

枚举子集

还是 Python 好

def subsets(S):
    if not S:
        return [[]]
    else:
        x, sub = S[0], subsets(S[1:])
        return sub + [([x]+s) for s in sub]

“翻译” 成 C++ 就有点难看了 (subset.cc)

• 语言没有内建的 List
• 用一个全局的数组更简单
  • 也是大家熟知的方式

枚举排列

def permutations(S):
    if not S:
        return [[]]
    else:
        res, perms = [], permutations(S[1:])
        for i, _ in enumerate(S):
            for perm in perms:
                res.append(perm[:i] + [S[0]] + perm[i:])
        return res

C++ 的 pure function 实现留作习题

• 这是一个很好的练习标准库的习题

枚举：一个非常强大的工具

枚举是万能的

• 枚举是我们定义问题的方式
  • 路径、生成树、排序、……
• 也是思考问题的出发点

枚举也是万万不能的

• 个元素集合的子集有 个……
• 在实际和竞赛中都需要更好的处理

经典时刻：The Tower of Hanoi

你们一定见过的代码

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << from << " -> " << to << endl;
    } else {
      hanoi(n - 1, from, aux, to);
      hanoi(1, from, to, aux);
      hanoi(n - 1, aux, to, from);
    }
}

把 个盘子从 移到

• 把 个盘子从 移到
• 把一个盘子从 移到
• 把 个盘子再从 移到

你真的理解递归了吗？

Quick Quiz

1. 你能实现一个非递归的汉诺塔吗？
   • (当然，不能借助数学性质)
2. 在 if (n == 1) 时，你能输出移动的盘子是第几个吗？
   • (当然，不能借助全局状态模拟)

是的，你没有真的理解递归！

hanoi() 与 Fibonacci 数列的区别

• 数学的函数 “不怕” 多次调用
  • 可以先算 ，再算
  • 甚至多调用几次

Tower of Hanoi 是不行的

• 多调用一次就错了
• 交换顺序也错了
  • 我们必须非常小心地考虑对全局的状态的影响！

划重点

问问人工智能 (voicegpt 登场)：

在编程时使用 pure function 避免副作用有什么好处？

愤怒的抱怨

• 我们编程竟然不教这个
• 老师们还不如人工智能
  • 是的！AI 写代码懂得这个道理！

回到 hanoi() 的问题

它没有真正解决问题

• 只能输出方案，不知道状态

它不是一个数学的函数

• cout 改变了 “函数外” 的部分

我们的问题：

• 实现一个真正解决问题的 hanoi()，而且是一个数学的函数
  • 在函数体里多调用几次也不会错
  • 应该输入什么、输出什么？

The Tower of Hanoi

是一个数学函数

• 输入：
  • 柱子上的所有盘子的位置分布 (状态 s)
  • 移动目标 (n, from, to)
  • 状态保证合法：有 n 个盘子可以移
• 返回：
  • 从 s 到目标状态逐步经过的所有中间状态 (列表)

“函数化” 使我们能用数学上习惯的方式思考程序的正确性

• 任何时候你都知道当前所有盘子的位置 (s)

看看代码

我们用了一点 C++ 的特性 (hanoi_r.cc)

• 但还是 Python 写起来更好
• list 支持加法
  • 看似 “舍近求远”
  • 但这是你真正可以理解和驾驭的代码

加一点挑战性

• 不仅输出状态
• 能不能真的把过程 “画出来”？(hanoi_main.cc)

愤怒地抱怨 (再一次)

为什么我们的老师对代码的质量视而不见？

• 正确使用 Modern C++ 特性
• 正确的编程方法
• 让大家爱上编程的方法

为什么他们明明知道，良心还不会痛？

• 或者良心痛了还是选择视而不见？

小结

纯函数 (pure function) 递归

• 与数学中的函数和递归完全一样
  • 一个 “输入 → 输出” 的盒子
  • 确定性：无论什么情况下执行多少次结果总是一样
• 只要保证终止，计算机总是能正确计算

好处

• 只用考虑 “输入什么、输出什么”
• 减轻了理解和实现的负担

如果都是 Pure Function，怎么实现递归？

都听说递归和栈有关系？

• 是 (但说来话长)
• 也不完全是

如果让你实现递归函数的计算？

• 调用的顺序和次序都无所谓！

递归树

既然 调用的顺序无所谓，递归也就好理解了

实现递归

任何时刻， 的 分成两类

• 我们已经计算出来的 (初始时，没有任何 被计算出来)
• 我们想计算的 (初始时，我们有一个想计算的 )

记住所有已经算出来的

• 对于任何想计算的 ，试着执行
  • 要么 能不递归直接算出，就记住
  • 否则 一定递归调用了某个没算出来的
    • 把 加入到 “想计算” 中
• 没有栈，依然是递归

Fibonacci Sequence

“记忆化” fib_nr.cc

• memorized 和 pending
• 人工智能新用处：学习代码

舍近求远？

• 我们从 0 到 n 循环不就行了？
  • memorized 在多次调用之间共享
  • 这个框架适用于任何 pure function 的递归实现

包括：汉诺塔

非递归，非栈，非数学方法

• “记住” 计算结果的版本 hanoi_nr.cc
• 用了一些现代 C++ 特性
  • std::optional, std::tuple
  • 不太好读，但又挺好读的

GPT-4-turbo 满分表现

move_disk：这个函数用于模拟将n个盘子从一个柱子移动到另一个柱子的过程，并返回移动后的状态。它首先将盘子从源柱子上取下，然后按正确的顺序放到目标柱子上。

we_know：这个函数检查给定的参数是否已经被计算过（即是否存在于memorized中）。如果已经计算过，返回true；否则，将该参数添加到pending集合中，并返回false。

hanoi_nr：这是解决汉诺塔问题的核心函数。它首先处理基本情况（即只有一个盘子时直接移动）。对于更多的盘子，它尝试将问题分解为三个步骤：……如果这三个步骤中的任何一个尚未计算，则函数返回nullopt；否则，它将这三个步骤的结果合并并返回。

hanoi：这个函数初始化汉诺塔问题，并反复尝试解决pending集合中的所有参数，直到没有剩余的参数。它首先将所有盘子放在第一个柱子上，然后将问题的初始参数添加到pending集合中。接着，它不断从pending集合中随机选择一个参数进行计算，直到集合为空。最后，它返回从初始状态到最终状态的所有步骤。

但是……

总感觉哪里不对

• 很 “浪费”，对不对？
  • “随机选择”
  • 调用 haon_nr 失败后，计算的中间结果都丢失了

有没有一个不用 “切来切去” 的实现方法？

回到递归树

我们可以按程序顺序生成递归树！

观察：不用记住递归树的全部

当递归 发生时

• 记住我们要回到什么样的程序状态 (参数、局部变量，和程序位置)
• 然后递归执行
• 递归返回后，恢复记住的程序状态 (参数、局部变量，和程序位置)
  • 允许随意破坏 “purity”，C++ 只是按 “自然顺序” 执行
  • 例子：汉诺塔里的 cout

时间有限，栈的资料网上很多，请大家自学

• 请听课的老师们消化这节课的内容
• 思考题：实现非递归 (栈版本) 的汉诺塔

小结

程序的顺序执行

• 定义了一个 “自然调用顺序”
• 我们其实在遍历一棵树

函数的栈帧：“局部状态”

• 参数
• 局部变量
• 函数返回时应该返回到的位置

递归

递归还是解构数学对象的基本方式

• 计算机科学中的很多 “Inductive Data Types” (归纳数据类型)
  • 从 Base Case 出发，不断构造出更多的新例子

自然数

• 是自然数
• 如果 是自然数，“” 也是自然数

更多 “归纳定义” 的例子

括号序列

• "" (空串) 是括号序列
• 如果 是括号序列，那么 () 也是括号序列
• 如果 是括号序列，那么 也是括号序列

表达式树

• 一个节点 (整数) 是表达式树
• 如果 , 是表达式树， 也是表达式树

例子：表达式求值

给一个字符串表示的表达式

• (1+2)*(3+4*5)
  • 方便处理，假仅包含一位数字、加法、乘法、括号
• 求它运算后的值

我们其实是在构建表达式树

• 找到最后一个运算的符号
• 递归 “构建表达式树”
  • eval.cc 和 Notebook

为什么要构建表达式树？

因为我们的目标不只是求值

• 可以根据 递归计算任何 的性质

出题时间到

• 求表达式的值
• 去除不必要的括号
• 如果允许把 个数字 +1，能得到的最大值

小结

归纳是构造计算机世界里一切的基本方法

• 递归是 “拆开” 归纳定义的基本方法

总结

第一节递归课

• 数学上的函数
• 计算机里的纯函数
  • 用 “数学” 的方式思考

递归与栈

• 栈恰好是数学递归的一个 “自然实现”
• 但并不是唯一的实现！