2024-09-11

UC Berkeley CS61a自学历程和学习总结 (4)

Part 15: Inheritance –继承

Inheritance is a method for relating classes together

继承是将多个类关联到一起的一种方法，因为并非每个类都孤立地存在。

A common use: Two similar classes differ in their degree of specialization.

1 2	class <name>(<base class>): <suite>

从概念上来讲，通过这个类语句创建的子类与其基类共享所有属性，子类可能会覆盖某些继承的属性，以稍微更改其行为，但未更改的然后内容均保持不变。使用继承时，当我们编写现有类的子类时，我们只需指定这个子类与基类有何不同。

举一个支票和银行账户的例子：

class CheckingAccount(Account):
    """A bank account that charges for withdrawals"""
    withdraw_fee = 1
    interest = 0.01
    def withdraw(self, amount):
        return Account.withdraw(self, amount + self.withraw_fee)

Looking Up Attribute Names on Classes

Base class attributes aren’t copied into subclasses!

To look up a name in a class:

If it names an attribute in the class, return the attribute value
Otherwise, look up the name in the base class, if there is one.

Object-Oriented Design

Designing for Inheritance

Don’t repeat yourself; use existing implementations
Attributes that have been overridden are still accessible via class objects
Look up attributes on instances whenever possible

Inheritance and Composition

Object-oriented programming shines when we adopt the metaphor
(That is, we treat objects like real things in the world.)
Inheritance is best for representing is-a relationships.
Composition is best for representing has-a relationships.

让我们快速搭建一个银行

class Account:
    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance = self.balance - amount
        return self.balance

class CheckingAccount(Account):
    """A bank account that charges for withdrawals"""
    withdraw_fee = 1
    interest = 0.01
    def withdraw(self, amount):
        return Account.withdraw(self, amount + self.withraw_fee)

class Bank():
    """A bank has accounts.
    >>> bank = Bank()
    >>> johh = bank.open_account('John', 10)
    >>> jack = bank.open_account('Jack', 5, CheckingAccount)
    >>> john.interest
    0.02
    >>> jack.interest
    0.01
    >>> bank.pay_interest()
    >>> john.balance
    10.2
    >>> bank.too_big_to_fail()
    True
    """

    def __init__(self):
        self.accounts = []
    
    def open_account(self, holder, amount, kind = Account):
        account = kind(holder)
        account.deposit(amount)
        self.accounts.append(account)
        return account

    def pay_interest(self)
        for a in self.accounts:
            a.deposit(a.balance * a.interest)

    def too_big_to_fail(self):
        return len(self.accounts) > 1

Attributes Lookup Practice

class A:
    z = -1
    def f(self, x):
        return B(x-1)

class B(A):
    n = 4
    def __init__(self, y):
        if y:
            self.z = self.f(y)
        else:
            self.z = C(y + 1)

class C(B):
    def f(self, x):
        return x

a = A()
b = B(1)
b.n = 5

思考一下的表达式的返回值是什么？

1
2
3

>>> C(2).n
>>> a.z == C.z
>>> a.z == b.z

同时思考以下哪些表达式是整数？

b.z
b.z.z
b.z.z.z
b.z.z.z.z

这些问题就先不给出答案了，如果大家能够自己独立推理出来，那对于继承，类，属性的掌握就比较不错了。

Multiple Inheritance

Multiple inheritance is when a subclass has multiple inheritance

class AsSeenOnTVAccount(CheckingAccount, SavingsAccount):
    def __init__(self, account_holder):
        self.holder = account_holder
        self.balance = 1  # A free dollar

一个类可以从多个基类继承。

Part16: Representations

String Representations

为了高效地展示数据，一个对象值应该像它代表的数据一样进行行为，包括产生一个它自己的字符串表示。在像 Python 这样的交互式语言中，数据值的字符串表示是特别重要的，在交互式会话中，它可以自动地展示表达式的值的字符串形式。

字符串值为人们提供了一种相互传递信息的基本媒介。字符序列可以渲染在屏幕上、打印在纸上、大声阅读出来、转换成盲文或者以莫斯码广播。字符串也是编程的基础，因为他们可以表示 Python 表达式。

Python 规定所有的对象都应该生成两个不同的字符串表示：一种是人类可读的文本，另一种是 Python 可解释的表示式。字符串的构造函数，即 str，返回一个人类可读的字符串。如果可能，repr 函数返回一个 Python 可解释的表达式，该表达式的求值结果与原对象相同。repr 的文档字符串（docstring）解释了这个特性：

repr(object) -> string

Return the canonical string representation of the object.

For most object types, eval(repr(object)) == object

返回对象的标准字符串表示。

对于大多数对象类型，eval(repr(object)) == object。

对于表达式的值调用 repr 的结果就是 Python 在交互式会话中所打印的内容。

>>> 12e12
12000000000000.0
>>> print(repr(12e12))
12000000000000.0

在一些情况下，不存在对原始值的字符串表示时，Python 通常生成一个被尖括号包围的描述。

1 2	>>> repr(min) '<built-in function min>'

A object value should behave like the kind of data it is meant to represent

In python, all objects produce two string representations:

The str is legible to humans.
The repr is legible to the Python interpreter.

>>> from fractions import Fraction
>>> half = Fraction(1, 2)
>>> half
Fraction(1, 2)
>>> repr(half)
'Fraction(1, 2)'
>>> print(half)
1/2
>>> str(half)
'1/2'
>>> eval(repr(half))
Fraciton(1, 2)
>>> eval(str(half))
0.5

str is a built-in function that takes any object, gives you back a string, where the string is some human interpretable representation of the original object

F-String

当你在 Python 中格式化字符串时，你可能习惯于使用 format() 方法。

但在 Python 3.6 和更高版本中，你可以使用 f-string 来代替。f-string，也被称为格式化字符串常量，有一个更简洁的语法，在字符串格式化中可以起到很大的作用。

F-Strings in Python are a feature that allow you to generate strings out of various expressions inside of a string literal

F-Strings允许你在字符串文字中生成各种表达式的字符串。

评估f-string文字的结果包含各个子表达式值的str string
子表达式是在当前环境里面评估的，这意味着你可以用连接构建的任何内容，也可以用字符串插值构造。

Syntax

1	f"This is an f-string {var_name} and {var_name}."

以下给出一些使用的实例：

1
2
3

num1 = 83
num2 = 9
print(f"The product of {num1} and {num2} is {num1 * num2}.")

1 2	#Output The product of 83 and 9 is 747.

在任何 f-string 中，{var_name}, {expression} 作为变量和表达式的占位符，并在运行时被替换成相应的值。

f-string还可以使用条件语句:

1 2	num = 87; print(f"Is num even? {True if num%2==0 else False}")

调用方法：

1 2	author = "jane smith" print(f"This is a book by {author.title()}.")

调用函数：

1	f'2 + 2 = {(lambda x: x + x)(2)}'

Polymorphic Functions– 多态函数

多态（英语：Polymorphism），是指面向对象程序运行时，相同的消息可能会送给多个不同的类之对象，
而系统可依据对象所属类，引发对应类的方法，而有不同的行为。
简单来说，所谓多态意指相同的消息给予不同的对象会引发不同的动作称之。
在面向对象程序设计中，多态一般指子类型多态（Subtype polymorphism）。

str and repr are both polymorphic

>>> half.__repr__()
'Fraction(1, 2)'

>>> half.__str__()
'1/2'

Interfaces –接口

Message passing: Object interact by looking up attributes on each other

语言的机制是查找属性和方法，这就是传递消息的概念。属性查找规则是以一种特殊的方式设计的，它们允许不同的数据类型通过相同属性名称来响应相同的消息。

共享消息，即存在于许多不同类上并引起这些不同类相同行为的属性名称，是一种强大的抽象方法。

一个接口是一组共享的消息和一些规范，告诉你它们应该做什么，代表着什么。

class Ratio:
    def __init__(self, n, d):
        self.numer = n
        self.denom = d

    def __repr__(self):
        return 'Ratio({0}, {1})'.format(self.numer, self.denom)
    
    def __str__(self):
        return '{0}/{1}'.format(self.numer,self.denom)

>>> half = Ratio(1, 2)
>>> Print(half)
1/2
>>> half
Ratio(1, 2)

Special Method Name

Certain names are special because they have built-in behavior
These names always start and end with two underscores
__init__ Method invoked automatically when an object is constructed
__repr__ Method invoked to display an objetc as a Python expression
__add__ Method invoked to add one object to another
__bool__ Method invoked to convert an object to True or False
__float__ Method invoked to convert an object to a float

>>> zero, one, two = 0, 1, 2
>>> one.__add__(two)
3
>>> zero.__bool__(), one.__bool__()
(False, True)

Part 17 Composition

Linked Lists

Linked list Structure

A linked list is either empty or a first value and the rest of the linked list.

链表 (Linked List) 由两个部分组成：第一个元素和链表剩下的部分。而剩下的这部分链表它本身就是个链表，这就是链表的递归定义法。其中，一个比较特殊的情况是空链表——他没有第一个元素和剩下的部分。

链表是一种序列 (sequence)：它具有有限的长度并且支持通过索引选择元素。

现在我们可以实现具有相同行为的类。在现在这个版本中，我们将使用专用方法名来定义它的行为，专用方法允许我们的类可以使用 Python 内置的 len 函数和元素选择操作符（方括号或 operator.getitem ）。这些内置函数将调用类的专用方法：长度由 __len__ 计算，元素选择由 __getitem__ 计算。空链表由一个长度为 0 且没有元素的空元组表示。

>>> class Link:
        """一个链表"""
        empty = ()
        def __init__(self, first, rest=()):
            assert rest == Link.empty or isinstance(rest, Link)
            self.first = first
            self.rest = rest
        def __getitem__(self, i):
            if i == 0:
                return self.first
            else:
                return self.rest[i-1]
        def __len__(self):
            return 1 + len(self.rest)
>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[1]
4

以上的 __len__ 和 __getitem__ 的定义都是递归的。Python 的内置函数 len 在它接收属于用户定义的类的实例时调用了__len__方法。类似地，元素选择操作符则会调用 __getitem__ 方法。因此，这两个方法定义的主体中都会间接的调用他们自己。对于 len 来说，基线条件 (base case) 就是当 self.rest 计算得到一个空元组，也就是 Link.empty 时，此时长度为 0。

内置的 isinstance 函数返回第一个参数的类型是否属于或者继承自第二个参数。isinstance(rest, Link) 在 rest 是 Link 的实例或 Link 的子类的实例时为 True。

我们对于链表的类定义已经很完备了，但是现在我们还无法直观地看到 Link 的实例。为了方便之后的调试工作，我们再定义一个函数去将一个 Link 实例转换为一个字符串表达式。

>>> def link_expression(s):
        """返回一个可以计算得到 s 的字符串表达式。"""
        if s.rest is Link.empty:
            rest = ''
        else:
            rest = ', ' + link_expression(s.rest)
        return 'Link({0}{1})'.format(s.first, rest)
>>> link_expression(s)
'Link(3, Link(4, Link(5)))'

用这个方法去展示一个链表实在是太方便了，以至于我想在任何需要展示一个 Link 的实例的时候都用上它。为了达到这个美好愿景，我们可以将函数 link_expression 作为专用方法 __repr__ 的值。Python 在展示一个用户定义的类的实例时，会调用它们的 __repr__方法。

1
2
3

>>> Link.__repr__ = link_expression
>>> s
Link(3, Link(4, Link(5)))

ink 类具有闭包性质 (closure property)。就像列表的元素可以是列表一样，一个 Link 实例的第一个元素也可以是一个 Link 实例。

1
2
3

>>> s_first = Link(s, Link(6))
>>> s_first
Link(Link(3, Link(4, Link(5))), Link(6))

链表 s_first 只有两个元素，但它的第一个元素是一个有着三个元素的链表。

>>> len(s_first)
2
>>> len(s_first[0])
3
>>> s_first[0][2]
5

递归函数特别适合操作链表。(以下所有函数均在列表类中编写！)

首先我们写一个range_link函数，来返回一个范围内的链表

def range_link(start, end):
    """Return a Link containing consecutive integers from start to end.

    >>> range_link(3, 6)
    Link(3, Link(4, Link(5)))
    """
    if start >= end:
        return Link.empty
    else:
        return Link(start, range_link(start + 1, end))

递归函数 extend_link 建立了一个新的链表，这个新链表是由链表 s 和其后边跟着的链表 t 组成的。将这个函数作为 Link 类的方法 add 就可以仿真内置列表的加法运算。

>>> def extend_link(s, t):
        if s is Link.empty:
            return t
        else:
            return Link(s.first, extend_link(s.rest, t))
>>> extend_link(s, s)
Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))
>>> Link.__add__ = extend_link
>>> s + s
Link(3, Link(4, Link(5, Link(3, Link(4, Link(5))))))

想要实现列表推导式 (List Comprehensions)，也就是从一个链表生成另一个链表，我们需要两个高阶函数：map_link 和 filter_link。其中 map_link 将函数 f 应用到链表 s 的每个元素，并将结果构造成一个新的链表。

>>> def map_link(f, s):
        if s is Link.empty:
            return s
        else:
            return Link(f(s.first), map_link(f, s.rest))
>>> map_link(square, s)
Link(9, Link(16, Link(25)))

函数 filter_link 返回了一个链表，这个链表过滤掉了原链表 s 中使函数 f 不返回真的元素，留下了其余的元素。通过组合使用 map_link 和 filter_link，我们可以达到和列表推导式相同的逻辑过程和结果。

>>> def filter_link(f, s):
        if s is Link.empty:
            return s
        else:
            filtered = filter_link(f, s.rest)
            if f(s.first):
                return Link(s.first, filtered)
            else:
                return filtered
>>> odd = lambda x: x % 2 == 1
>>> map_link(square, filter_link(odd, s))
Link(9, Link(25))
>>> [square(x) for x in [3, 4, 5] if odd(x)]
[9, 25]

函数 join_link 递归的构造了一个包含着所有在链表里的元素，并且这些元素被字符串 separator 分开的字符串。这个结果相较于 link_expression 来说就更加简练。

>>> def join_link(s, separator):
        if s is Link.empty:
            return ""
        elif s.rest is Link.empty:
            return str(s.first)
        else:
            return str(s.first) + separator + join_link(s.rest, separator)
>>> join_link(s, ", ")
'3, 4, 5'

Linked Lists Can Change

>>> s = Link(1, Link(2, Link(3)))
>>> s.first = 5
>>> t = s.rest
>>> t.rest = s
>>> s.first
5
>>> s.rest.rest.rest.rest.rest.first
2

这个例子为我们展示链表元素被改变的一个实例。第一次看可能会被这种操作搞得眼花缭乱，我个人习惯是对于链表，是画个图，看到赋值语句，从左到右读，把左边的元素指向右边元素的储存单元，这样就不会弄混了。

Recursive Construction

当以增量方式构造序列时，链表特别有用，这种情况在递归计算中经常出现

第一章我们介绍过的函数 count_partitions 通过树递归计算了使用大小最大为 m 的数对整数 n 进行分区的方法的个数。通过序列，我们还可以使用类似的过程显式枚举这些分区。

与计数方法个数的方法相同，我们利用相同的递归统计方法：将一个数 n 在最大数限制为 m 下分区包含两种情况：

用 m 及以内的整数划分 n-m
用 m-1 及以内的整数划分 n
对于基线情况，我们知道 0 只有一个分区方法，而划分一个负整数或使用小于 1 的数划分是不可能的。

>>> def partitions(n, m):
        """Return a linked list of partitions of n using parts of up to m.
        Each partition is represented as a linked list.
        """
        if n == 0:
            return Link(Link.empty) # A list containing the empty partition
        elif n < 0 or m == 0:
            return Link.empty
        else:
            using_m = partitions(n-m, m)
            with_m = map_link(lambda s: Link(m, s), using_m)
            without_m = partitions(n, m-1)
            return with_m + without_m

在递归情况下，我们构造两个分区子列表。第一个使用 m，因此我们将 m 添加到 using_m 的结果的每个元素中以形成 with_m。

分区的结果是高度嵌套的：是一个链表的链表。使用带有适当分隔符的 join_link，我们可以以易读的方式显示各个分区。

>>> def print_partitions(n, m):
        lists = partitions(n, m)
        strings = map_link(lambda s: join_link(s, " + "), lists)
        print(join_link(strings, "\n"))
>>> print_partitions(6, 4)
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

Linked List Mutation Example

Adding to an Ordered List

def add(s, v):
    """Add v to an ordered list s with no repeats, returning modified s."""
    (Note: If v is already in s, then don't modify s, but still return it.)

    assert s is not List.empty
    if s.first > v:
        s.first, s.rest = v, Link(s.first, s.rest)
    elif s.first < v and empty(s.rest):
        s.rest =  Link(v)
    elif s.first < v:
        add(s.rest, v)
    return s

Tree Class

树是另外一个递归计算的数据结构，我们其实已经单独花了一个部分来讲Tree了，但是树实在是太过于重要了，我们需要再次谈论它。

树也可以用用户定义的类的实例来表示，而不是内置序列类型的嵌套实例。树是具有作为属性的分支序列的任何数据结构，同时，这些分支序列也是树。

内部值在树中称为 label。下面的 Tree 类就表示这样的树，其中每棵树都有一系列分支，这些分支也是树。

>>> class Tree:
        def __init__(self, label, branches=()):
            self.label = label
            for branch in branches:
                assert isinstance(branch, Tree)
            self.branches = branches
        def __repr__(self):
            if self.branches:
                return 'Tree({0}, {1})'.format(self.label, repr(self.branches))
            else:
                return 'Tree({0})'.format(repr(self.label))
        def is_leaf(self):
            return not self.branches

简单解释一下
Tree 类用来创建一个树结构，label 表示节点的值，branches 表示节点的分支，分支也是 Tree 对象。

__repr__ 方法用于显示树的结构。

is_leaf 用来检查当前节点是否为叶子节点（没有子节点）。

例如，Tree 类可以表示 用于计算斐波那契数的函数 fib 的递归表达式树中计算的值。下面的函数 fib_tree(n) 返回一个 Tree 的实例，该实例以第 n 个斐波那契数作为其 label，并在其分支中跟踪所有先前计算的斐波那契数。

>>> def fib_tree(n):
        if n == 1:
            return Tree(0)
        elif n == 2:
            return Tree(1)
        else:
            left = fib_tree(n-2)
            right = fib_tree(n-1)
            return Tree(left.label + right.label, (left, right))
>>> fib_tree(5)
Tree(3, (Tree(1, (Tree(0), Tree(1))), Tree(2, (Tree(1), Tree(1, (Tree(0), Tree(1)))))))

并且，Tree 类的实例也可以用递归函数进行处理。例如，我们可以对树的 label 求和。

>>> def sum_labels(t):
        """对树的 label 求和，可能得到 None。"""
        return t.label + sum([sum_labels(b) for b in t.branches])
>>> sum_labels(fib_tree(5))
10

我们也可以用 memo 去构造一个斐波那契树。有了它，重复的子树只会被记忆版本的 fib_tree 创建一次，然后在不同大小的树中被用作分支很多次。

>>> fib_tree = memo(fib_tree)
>>> big_fib_tree = fib_tree(35)
>>> big_fib_tree.label
5702887
>>> big_fib_tree.branches[0] is big_fib_tree.branches[1].branches[1]
True
>>> sum_labels = memo(sum_labels)
>>> sum_labels(big_fib_tree)
142587180

Part 18: Efficiency

Measuring Efficency –测量效率

测量程序运行所需的时间或消耗的内存确切值是具有挑战性的，因为结果取决于计算机配置的许多细节。更可靠地表征程序的效率的方法是测量某些事件发生的次数，例如函数调用次数。

我们第一个树递归的例子，是使用树递归来计算斐波那契数列元素的方法。采用以下实现

>>> def fib(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return fib(n - 2) + fib(n - 1)
>>> fib(5)
5

考虑计算 fib(6) 时的计算模式，如下所示，为了计算 fib(5)，我们计算 fib(3) 和 fib(4)。而要计算 fib(3)，我们需要计算 fib(1) 和 fib(2)。

这个函数作为一个典型的树递归函数具有教学意义，但它是计算斐波那契数的一种极其低效的方式，因为它进行了大量的冗余计算。计算 fib(3) 的整个过程被重复执行。

我们可以测量这种低效性。这个高阶的 count 函数返回一个与其参数等效的函数，并且还维护一个 call_count 属性。通过这种方式，我们可以检查 fib 函数被调用的次数。

>>> def count(f):
        def counted(n):
            counted.call_count += 1
            return f(n)
        counted.call_count = 0
        return counted

简单解释一下这个函数的实施吧：

count(f) 是一个装饰器，接收一个函数 f 作为参数。
在 count 内部定义了一个嵌套函数 counted(n)，每次调用 counted(n)，都会执行 counted.call_count += 1，即自增计数器。
counted.call_count = 0 初始化了 call_count 这个属性。这里利用了 Python 函数对象的特性，可以为函数对象动态添加属性。
最后 count 函数返回的是 counted，这个闭包保存了传入的 f 函数，并且可以通过 counted.call_count 记录它的调用次数。

通过计算对 fib 函数的调用次数，我们可以发现所需的调用次数增长速度比斐波那契数列本身还要快。这种调用的快速增长是树递归函数的特征。

>>> fib = count(fib)
>>> fib(19)
4181
>>> fib.call_count
10946

Memoization

Memoization is an extremely useful technique for speeding up the running time of a program.

Idea: Remember the results that have been computed before

记忆化可以自然地表达为一个高阶函数，也可以用作装饰器。下面的定义创建了一个缓存（cache），用于存储先前计算过的结果，索引是它们计算所用的参数。使用字典作为缓存的数据结构要求被记忆化的函数的参数是不可变的。

>>> def memo(f):
        cache = {}
        def memorized(n):
            if n not in cache:
                cache[n] = f(n)
            return cache[n]
        return memorized

通过使用 count 函数，我们可以看到对于每个唯一的输入，fib 函数实际上只被调用一次。核心就在于我存储了我计算过的内容。

>>> counted_fib = count(fib)
>>> fib =memo(count_fib)
>>> fib(19)
4181
>>> counted_fib.call_count
20
>>> fib(34)
5702887
>>> counted_fib.call_count
35

Exponentiation–取幂

Linear time(线性时间):

Doubling the input doubles the time
1024x the input takes 1024x as much time

Logarithmic time(对数时间):

Doubling the input increases the time by a constant C
1024x the input increases the time by only 10 times C

比如我们要计算一个数的幂方，以下分别呈现两种效率的函数实现方法。

def exp(b, n):
    if n == 0:
        return 1
    else:
        return b * exp(b, n-1)

def exp_fast(b, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return square(exp_fast(b, n//2))
    else:
        return b * exp_fast(b, n-1)

def square(x)
    return x * x

Order of Growth Notation

增长阶是为了简化计算过程的分析和比较而设计的。许多不同的计算过程可以具有等效的增长阶，这表示它们的增长方式相似。对于计算机科学家来说，了解和识别常见的增长阶并确定具有相同增长阶的过程是一项重要的技能。

类型	$\Theta$表示	增长阶描述	例子
常数	$\Theta(1)$	增长与输入无关	`abs`（绝对值函数）
对数	$\Theta(\log_{n})$	增长与输入规模的对数成正比	`binary search`（二分查找）
线性	$\Theta(n)$	随着输入的递增，计算过程所需的资源成比例增长	`for loop`（线性循环）
平方	$\Theta(n^2)$	随着输入的递增，计算过程所需的资源增加为输入的平方	`矩阵乘法`
指数	$\Theta(2^n)$	随着输入的递增，计算过程所需的资源成倍增长	`fib`（递归斐波那契）

Space

Which environment frames do we need to keep during evaluation?

空间。要了解函数的空间需求，我们通常必须指定在计算的环境模型中如何使用、保留和回收内存。在计算表达式时，解释器会保存所有活动的环境，以及这些环境引用的所有值和帧。我们称一个环境是活动的，如果它为正在计算的某个表达式提供了评估上下文。每当为其创建第一个帧的函数调用最终返回时，环境将变为非活动状态。

例如，在计算 fib 时，解释器按照之前显示的顺序计算每个值，遍历树的结构。为此，它只需要跟踪在计算的任何时刻位于当前节点上方的那些节点。用于计算其他分支的内存可以被回收，因为它不会影响未来的计算。总的来说，树递归函数所需的空间将与树的最大深度成比例。

高阶函数 count_frames 用于跟踪尚未返回的函数调用次数 open_count 。它通过在计算过程中记录当前活动的函数调用次数来实现。max_count 属性是 open_count 曾经达到的最大值，它对应于在计算过程中同时处于活动状态的最大帧数。

>>> def count_frames(f):
        def counted(n):
            counted.open_count += 1
            counted.max_count = max(counted.max_count, counted.open_count)
            result = f(n)
            counted.open_count -= 1
            return result
        counted.open_count = 0
        counted.max_count = 0
        return counted
>>> fib = count_frames(fib)
>>> fib(19)
4181
>>> fib.open_count
0
>>> fib.max_count
19
>>> fib(24)
46368
>>> fib.max_count
24

总结一下， fib 函数的空间要求（以活动帧数衡量）比输入小一个单位，这往往是较小的。

-------------本文结束感谢您的阅读-------------

本文作者： Arua
本文链接： https://blog.visionary-5.top/2024/09/11/CS61A%E7%BC%96%E7%A8%8B%E8%AF%AD%E8%A8%80%E8%AF%BE%E8%87%AA%E5%AD%A6%E5%8E%86%E7%A8%8B(4)/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！