如果我们不允许你在函数里引入副作用
有一个名字:“pure function” (纯函数)
自己可以引用自己的函数
C++ 也支持这样的表达 (fibonacci.cc)
int f(int n) {
if (n <= 1) return n;
return f(n - 1) + f(n - 2);
}
计算机的函数允许一切 “复合数字”
例子:
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)
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 实现留作习题
枚举是万能的
枚举也是万万不能的
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
if (n == 1)
时,你能输出移动的盘子是第几个吗?
是的,你没有真的理解递归!
Tower of Hanoi 是不行的
问问人工智能 (voicegpt 登场):
在编程时使用 pure function 避免副作用有什么好处?
愤怒的抱怨
它没有真正解决问题
它不是一个数学的函数
我们的问题:
“函数化” 使我们能用数学上习惯的方式思考程序的正确性
我们用了一点 C++ 的特性 (hanoi_r.cc)
加一点挑战性
为什么我们的老师对代码的质量视而不见?
为什么他们明明知道,良心还不会痛?
纯函数 (pure function) 递归
好处
都听说递归和栈有关系?
如果让你实现递归函数的计算?
既然
任何时刻,
记住所有已经算出来的
“记忆化” fib_nr.cc
舍近求远?
非递归,非栈,非数学方法
std::optional
, std::tuple
move_disk:这个函数用于模拟将n
个盘子从一个柱子移动到另一个柱子的过程,并返回移动后的状态。它首先将盘子从源柱子上取下,然后按正确的顺序放到目标柱子上。
we_know:这个函数检查给定的参数是否已经被计算过(即是否存在于memorized
中)。如果已经计算过,返回true
;否则,将该参数添加到pending
集合中,并返回false
。
hanoi_nr:这是解决汉诺塔问题的核心函数。它首先处理基本情况(即只有一个盘子时直接移动)。对于更多的盘子,它尝试将问题分解为三个步骤:……如果这三个步骤中的任何一个尚未计算,则函数返回nullopt
;否则,它将这三个步骤的结果合并并返回。
hanoi:这个函数初始化汉诺塔问题,并反复尝试解决pending
集合中的所有参数,直到没有剩余的参数。它首先将所有盘子放在第一个柱子上,然后将问题的初始参数添加到pending
集合中。接着,它不断从pending
集合中随机选择一个参数进行计算,直到集合为空。最后,它返回从初始状态到最终状态的所有步骤。
总感觉哪里不对
haon_nr
失败后,计算的中间结果都丢失了有没有一个不用 “切来切去” 的实现方法?
我们可以按程序顺序生成递归树!
当递归
时间有限,栈的资料网上很多,请大家自学
程序的顺序执行
函数的栈帧:“局部状态”
递归还是解构数学对象的基本方式
自然数
括号序列
""
(空串) 是括号序列(
)
也是括号序列表达式树
给一个字符串表示的表达式
(1+2)*(3+4*5)
我们其实是在构建表达式树
因为我们的目标不只是求值
出题时间到
归纳是构造计算机世界里一切的基本方法
第一节递归课
递归与栈
End. (Notebook)