2024-09-05

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

Part 7: Recursion–递归

Self_Reference

在自然语言或形式语言formal language中，当一个句子、想法或公式指向自己时，就会出现自指现象 Self-reference。自指Self-reference经常在数学，哲学，计算机编程和语言学中被研究和应用。自指陈述有时是自相矛盾的，也可以被认为是递归的。实现递归往往离不开自指。
我们以下面两个基本的以print构成的函数为例子

def print_all(x):
    print(x)
    return print_all    

print_all(1)(3)(5)

def print_sums(x):
    print(x)
    def next_sum(y):
        return print_sums(x + y)
    return next_sum
print_sums(1)(3)(5)

第一个函数print_all，本质上就是通过传递形参x进去，不断地返回自身，来实现一个全部输出的作用，而第二个函数通过嵌套定义函数，则依次实现了参数的相加，最终把相加的过程值打印出来。

Recursive_function

Definition:A function is caller recursive if the body of that function calls itself, either directly or indirectly

Implication:Executing the body of a recursive function may require applying that function again

def split(n):
    return n // 10, n % 10

def sum_digits(n):
    if  n < 10:
        return n
    else:
        all_but_last, last = split(n)
        return sum_digits(all_but_last) + last

Multural_recursion–相互递归

以卢恩算法为例，该校验方法适用于任何标准信用卡。校验方法：
从右边开始，将偶数位的数字乘以 2；
将得到的数字和刚才剩余的（奇次位）的所有数字相加，如果遇到乘以 2 后得到的数字是 2 位数的，则将其个位和十位数相加；
如果得到的数字之和是 10 的倍数，则号码为真，否则就是假的信用卡号了。

"""The luhn algorithm 卢恩算法"""

def split(n):
    return n // 10, n % 10

def sum_digits(n):
    if  n < 10:
        return n
    else:
        all_but_last, last = split(n)
        return sum_digits(all_but_last) + last
    
def luhn_sum(n):
    if n < 10:
        return n
    else:
        all_but_last, last = split(n)
        return luhn_sum_double(all_but_last) + last
    
def luhn_sum_double(n):
    all_but_last, last = split(n)
    luhn_digit = sum_digits(2 * last)
    if n < 10:
        return luhn_digit
    else:
        return luhn_sum(all_but_last) + luhn_digit

Iteration_vs_Recursion–递归or迭代？

Iteration is a special case of recursion
迭代是一种特殊的递归函数

The Recursive Leap of Faith: Is fact implemented corrctily(递归的信仰之跃，挺有意思的)

Verify the base case.
Treat fact as a functional abstraction!
Assume that fact(n-1) is correct.
Verify that fact(n) is correct, assuming that fact(n-1) correct.

"""Using_while:"""
def fact_iter(n):
    total,k = 1, 1
    while k <= n:
        total, k = total * k, k + 1
    return total

"""Using recursion"""
def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

Tree Recursion

Tree-shaped processes arise whenever execuitng the body a recursive function makes more than one call to the function.
每当执行递归函数的主题使得对该函数的调用超过一次,树形递归会产生树状过程，

又回到我们最为熟悉的fibnacci数列：

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

整个函数的调用就像一个树状结构一样，通过不断地自我指代，最终求出我们想要的那个结果，我们可以用python tutor来观察这个环境图，更为详细和直观地了解整个过程。当然我们必须主要到，如果我们要计算一个非常大的数的斐波那契数列，那么我们要通过大量地递归重复才能计算出来，这非常浪费计算资源，也会降低计算速度，所以这个代码虽然简单，但是其实并不是最为高效的。

Counting_partitions

The number of partitions of a postive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order

简单地来说就是总数为n，用不超过m的数来给n分区，看一共有多少种情况，方法呢就是看n能够以不同方式表示为不超过m的部分的递增顺序之和

我们的思路是什么呢？在递归学习中，我们要寻找问题的递归分解，我们需要用较简单的相同类型的问题的实例来表达这个问题，也就是找出问题的通用策略。

化成简单的相同类型的问题本质就是拆分，比如说我有6个区域，以不超过4的大小来进行区域划分，那我们可以表示为(6, 4),那(6, 4)就可以拆分成两种情况：一种是我们至少包含一个四组，另一种是我们永远不会在分区中包含4，我们只会用大小为3或者更小的是更小的部分。

观察一下，我们可以发现，凡是包含一组4的，实际上只需要在减去4之后剩下的部分进行划分，本质上就是划分数字2，（也是用不超过4的组去划分），记作(2,4)。

另一方面我们就是在分割6除了用区域4之外的所有情况。很简单就是记作(6,3),最后我们发现不管怎么分区，我们都可以这样拆分，代码如下。

def count_partitions(n, m):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        with_m = count_partitions(n-m, m)
        whth_out_m = count_partitions(n, m - 1)
        return whth_out_m + with_m

分区问题，完成！

Improve Fib

要改进递归计算斐波那契数列的效率问题，可以使用动态规划或者记忆化递归。这两种方法可以避免重复计算，提高效率。以下是使用记忆化递归（也称为缓存）的版本：

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
        return memo[n]

不过这里已经涉及到字典了，课程这部分还没讲到。

Cascade and Inverse_cascade

以下代码演示了如何递归地打印一个数字的层叠（cascade）和反向层叠（inverse cascade），并通过递归调用来控制数字的逐步缩减和扩展。

def cascade(n):
    if n < 10:
        print(n)  # 当 n 是一位数时，直接打印
    else:
        print(n)        # 打印当前数字
        cascade(n // 10)  # 递归调用，逐步缩小 n
        print(n)        # 打印当前数字，形成对称结构

调用 cascade(12345) 的输出为：

inverse_cascade(n) 函数：这个函数实现了反向层叠打印，并结合了两个辅助函数 grow 和 shrink：

def inverse_cascade(n):
    grow(n)
    print(n)
    shrink(n)
    
def f_then_g(f, g, n):
    if n:
        f(n)
        g(n)
        
grow = lambda n: f_then_g(grow, print, n // 10)
shrink = lambda n: f_then_g(print, shrink, n // 10)

调用 inverse_cascade(12345) 的输出为：

这段代码的结构非常巧妙，通过递归实现了对数字的层叠和反向层叠的效果。

Part 8 Sequence–序列

list

为了使我们能够实现具体的数据抽象，Python 提供了一个名为 list 列表的复合结构，可以通过将表达式放在以逗号分隔的方括号内来构造。这样的表达式称为列表字面量。

1 2	>>> [10, 20] [10, 20]

可以通过两种方式访问列表元素。第一种方法是通过我们熟悉的多重赋值方法，它将列表解构为单个元素并将每个元素与不同的名称绑定。

>>> pair = [10, 20]
>>> pair
[10, 20]
>>> x, y = pair
>>> x
10
>>> y
20

Python 中的列表（以及大多数其他编程语言中的序列）是从 0 开始索引的，这意味着索引 0 选择第一个元素，索引 1 选择第二个元素，以此类推。对于这种索引约定的一种直觉是，索引表示元素距列表开头的偏移量。

元素选择运算符的等效函数称为 getitem ，它也使用 0 索引位置从列表中选择元素。

>>> from operator import getitem
>>> getitem(pair, 0)
10
>>> getitem(pair, 1)
20

列表的元素可以是任何东西，包括列表

>>> pairs = [[10, 20], [30, 40]]
>>> pairs[1]
[30, 40]
>>> pairs[1][0]
30

Containers

Definition:Built-in operators for testing whether an element in a compound value

>>> digits = [1, 8, 2, 8]
>>> 1 in digits
True
>>> 8 in digits
True
>>> 5 not in digits
True
>>> not(5 in digits)
True
>>> [1, 8] in digits
False
>>> [1, 2] in [3, [1, 2], 4]
True

For Statements

迭代语句：在list列表中，我们可以用for…in…来遍历列表中的所有的元素，用来代替while语句，更加简洁高效。如果我们用while语句，还需要添加像index这样的检索变量，比较麻烦。

def count(s, value):
    """Count the number of times that value occurs in sequence S.
    
    >>> count([1,2,1,2,1], 1)
    3
    """
    total = 0
    for element in s:
        if element == value:
        total += 1  
    return total

Syntax tips:

1 2	def <name> in <expression>: <suite>

Evaluate the header expression, which must yield an iterable value (a sequence)
第一件事是评估标题表达式，这个表达式必须产生一个可迭代的值。
For each element in that sequence, in order: Bind name to that element in the current frame and execute the suite
对于序列中的每个元素，我们将把该名字绑定到当前帧中的元素上，然后执行该套件。

Sequence Unpacking in For Statements

>>> pairs = [[1, 2], [2, 2], [3, 2], [4, 4]]
>>> same_count = 0

>>> for x, y in pairs:
        if x == y:
            same_count = same_count + 1

>>> same_count
2

In this case, x, y are the name for each element in a fixed-length sequence

Ranges

Definition: A range is a sequence of consecutive integers.

Length: ending value - startting value

Element selection: starting value + index

List constructor

>>> list(range(-2, 2))
[-2, -1, 0, 1]

>>> list(range(4))"""Range with a 0 starting value"""
[0, 1, 2 ,3]

def sum_below(n):
    total = 0
    for i in range(n):
        total += i
    return total

List Comprehensions – 列表推导

>>> odds = [1, 3, 5, 7, 9]
>>> [x+1 for x in odds]
[2, 4, 6, 8, 10]
>>> [x for x in odds if 25 % x == 0]
[1, 5]
>>> [x+1 for x in odds if 25 % x == 0]
[2, 6]

比如我们可以写一个函数列举出一个数字的因数

1 2	def divisors(n): return [1] + [x for x in range(2, n) if n%x == 0]

Part 9 Containers

Box and Pointer Notation–方框和指针表示法

The Closure Property of Data Types–数据类型的闭包属性

A method for combining data values satisfies the closure property if: The result of combination can itself be combined using the same method.
如果组合数据值的方法满足这个封闭属性，那么组合的结果本身可以使用相同的方法再次组合。
Closure is powerful becease it permits us to create hierarchical structures.
封闭是强大的，因为它允许我们创建分层结构。
Hierarchical structures are made up of parts, which themselves are made up of parts, and so on
分层结构由部分组成，这些部分本身由由部分组成，依此类推。

1	nested_list = [[1, 2],[],[[3, False, None],[4,lambda: 5]]]

Slicing

Slicing is an operaiton that you can perform on sequences such as lists and ranges

""" I need ways to select out 5 and 7 """
>>> odds = [3, 5, 7, 9, 11]
>>> list(range(1, 3))
[1, 2]
>>> [odds[i] for i in range(1, 3)]
[5, 7]
>>> odds[1:3] #same rules with range
[5, 7]  
>>> odds[:3]
[3, 5, 7]
>>> odds[1:]
[5, 7, 9, 11]
>>> odds[:]
[3, 5, 7, 9, 11]

Slicing always creats new values

意味着你可以通过切片为不同的变量赋值

Processing Container Values – 处理容器值

Processing container values ofen involves iterating over all of the values contained in the list or dictionary that you are interested in

Sequence Aggregation(序列聚合):Sereral built-in function take iterable arguments and aggregate them into a value

sum(iterable[,start]) –> value
(doesn’t work with strings)

>>> sum([2, 3, 4])
9
>>> sum([2, 3, 4], 5)
14
>>> sum([[2, 3],[4]],[]) #只有首先提供一个列表才能进行计算，不然的话初始值会自动赋值为0导致整数和列表的不可相加问题。
[2, 3, 4]

max(iterable[, key=func]) -> value
max(a, b, c, …[,key = func]) -> value

(如何理解这个key function,你可以理解为它对你考虑的每一个元素应用一个函数，并根据调用这些函数的返回值实际计算出最大值)

With a single iterable argument, return its largest item.
With two or more arguments, return the largest argument.

>>> max(range(5))
4
>>> max(0, 1, 2, 3, 4)
4
>>> max(range(10), key = lambda x: 7-(x-4)*(x-2))
#如果我将这个指定为我的关键函数，那么它将告诉我在这个范围内调用这个函数的输出的最大值是3
3

all(iterable) - > bool
Return True if bool(x) is True for all values x in the iterable.If the iterable is empty,return True

我们学过布尔表达式是判断一个表达式是真值还是假值的一个表达式，如果是真值，返回True,如果是假值，则返回False。自然数0是一个假值，空字符串也是假值，而all函数就判断一个可迭代的对象是真值还是假值。例子如下：

>>> all([x < 5 for x in range(5)])
True
>>> all(range(5))
False

内置还有min和any函数，是max和all函数的补充。

String

String are an abstraction

字符串的表示可以用单引号，也可以用双引号，还可以用三引号，三引号可以延申到多行。

String are sequences

length and element selection are similar to all sequences

>>> city = 'Berkeley'
>>> len(city)
8
>>> city[3]
'k'

Careful: An element of a string is itself a string, but with only one element!

However, the “in” and “not in” operators match substrings

>>> 'here' in "Where 's Waldo?"
True
>>> 234 in [1, 2, 3, 4, 5]
False
>>> [2, 3, 4] in [1, 2, 3, 4, 5]
False

Dictionaries

Dictionaries are a built-in data type in Python that hould pairs of a key,which is what you use to look something up,which is what you use to look up a value,and the corresponding value

Dictionaries are collections of key-value pairs

Dictionary keys do have two restrictions:

A key of a dictionary cannot be a list or a dictionary (or any mutable type)
Two keys cannot be equal; There can be at most one value for a given key.

This first restriction is tied to Python’s underlying implementation of dictionaries.

This second restriction is part of the dictionary abstraction,which is that it’s supposed to give you the value for a key.

Dictionay Comprehensions

1	{ <key exp>: <value exp> for <name> in <iter exp> if <filter exp> }

1	{x * x: x for x in [1, 2, 3, 4, 5] if x > 2}

evaluates to {9: 3, 16: 4, 25: 5}

Example:Index

Implement index, which takes a sequence of keys, a sequence of values, and a two-arugument match function. It returns a dictionary from keys to lists in which the list for a key k contains all values v for which matchi(k, v) is a ture value

def index(keys, values, match)
"""Return a dictionary from keys k to a list of values v for which match(k, v)
is a true value.

>>>index([7, 9, 11], range(30, 50), lambda k, v: v % k == 0)
{7: [35, 42, 49], 9: [36, 45], 11: [33, 44]}
"""

return  {k: [v for v in values if match(k,v)] for k in keys}

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

本文作者： Arua
本文链接： https://blog.visionary-5.top/2024/09/05/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(2)/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！