LOADING

加载过慢请开启缓存 浏览器默认开启

CS61A学习总结

1. 数据抽象

使用函数构建抽象的·过程即将不同的作用代码抽象为一个个函数名称,将关注点从里面具体的代码实现转移到函数的作用,只需理解一个函数的需要的参数,输出的结果类型,发挥的作用即可。

使用数据构建抽象的过程大致可分为三个部分:

  1. 操作抽象数据
  2. 定义具体表示
  3. 一组根据具体表示实现抽象数据的函数将两部分相连
    解释:
    (1)操作抽象数据即构建的数据结构中操作的函数
    eg:List里的Add(),Detele()
    (2)定义具体表示即所抽象出来的数据的具体,用户是如何定义这个数据结构的
    eg:Point定义为有x,y坐标的一个点
    (3)相连部分即如何根据实际数据构建起抽象数据的函数,也就是构造函数和选择函数

2. 递归

递归的构建集中于三个点:

  1. Base case
    递归退出的条件,亦或者是递归可以进入的最小值 ,作为退出递归的条件

  2. Recursive call on a smaller problem
    递归逐渐减小的问题,关注递归如何通过逐渐减小来把一个问题逐渐变简单

  3. Solve the larger problem
    如何将一个个逐渐减小难度的问题集合在一起,从而形成一个大问题的答案

注1:Base case的情况(退出递归)的增加可以有效减少递归的深度
注2:尾递归指只在一次步骤中进行所有递归操作,部分编译器可以对尾递归进行优化,从而降低深度、

2. 尾递归

尾递归的原理是通过一个内置helper Function的函数,将当前调用的函数转化为一个helper Function,调用返回的是一个无参函数,从而结束了当前帧。而在帮助函数里,它返回它外面的函数,而这个外面的函数再次返回的仍然是一个helper Function,从而继续结束当前帧,如此循环(也就是将这个函数包装起来了,thunk)
再通过另一个拆包的函数来实现调用,一个简单循环如果拆开的函数仍然是一个thunk则继续拆包,知道拆出来的是一个value(Trampolining)

一个包装函数和一个拆包函数相互作用,从而在尾递归调用中减少了大量中间帧的保持。

尾递归的定义:在调用递归函数其本身前不做其他任何事情

3. Scheme解释器思考记录

为了在scheme解释器里面实现尾递归的优化,需要在评估一个函数时,确定其是否为一个尾递归还是一个普通递归,如果其为尾递归则对其单独处理。
利用打包函数将尾递归的多次调用封装在一个每次循环return的调用中,从而减少了中间帧的保持,再将其递交给拆包函数,实现返回

注意封装函数的过程不是一次性完成的,而是利用一个函数里面的helper Function来实现一个类似互递归的过程。在每次拆包时的评估过程中如果满足条件就再次封装

借助非连续的封装过程,可以在每次封装时确定当前调用是否为尾递归调用,从而实现一个递归函数的部分尾递归优化

注:避免使用递归语句实现函数的功能,可能导致即便尾递归优化了但然后回溢出

Scheme项目尾递归优化的实现:
在if,or,and语句判断中将满足条件的尾递归语句封装为Unevaluated(即代表一个延迟评估的表达式,在优化eval中的helperFunction中),在eval_all中,同样如此