日拱一卒，伯克利教你学递归，只用几道题让你登堂入室

TechFlow-承志

发布于 2022-08-26 14:43:49

3420

发布于 2022-08-26 14:43:49

文章被收录于专栏：TechFlow

作者 | 梁唐

大家好，日拱一卒，我是梁唐。

今天我们继续来看伯克利CS61A的作业4，这一期的课程没有太多新的内容，主要讲解的是分层设计和实现的编程习惯，质量很高，非常推荐大家去听一下。

这一次的作业依然质量很高，难度也稍微有些回落，比上次的作业3要简单一些。看起来吃力的话可以点击【阅读原文】跳转GitHub，原链接：https://inst.eecs.berkeley.edu//~cs61a/sp18/hw/hw04/

好了，废话不多说，我们来看题吧。

Q1: Taxicab Distance

曼哈顿距离也叫taxicab距离，在二维平面当中，我们通常用(x, y)来表示坐标，曼哈顿距离是计算两个坐标之间距离的一种方式。即

d = |x_1 - x_2| + |y_1 - y_2|

。

这种计算方式据说来源于美国曼哈顿地区的地址表示，在曼哈顿地点通常表示成Street和Avenue。只能横着或竖着穿越block。比如时代广场位于46th Street，7th Avenue，如果把Street和Avenue分别看成是坐标轴中的两个轴的话，那么时代广场的坐标就是(46, 7)。

这道题要实现的方法叫做taxicab，即计算两个坐标的曼哈顿距离。

def intersection(st, ave):
    """Represent an intersection using the Cantor pairing function."""
    return (st+ave)*(st+ave+1)//2 + ave

def street(inter):
    return w(inter) - avenue(inter)

def avenue(inter):
    return inter - (w(inter) ** 2 + w(inter)) // 2

w = lambda z: int(((8*z+1)**0.5-1)/2)

def taxicab(a, b):
    """Return the taxicab distance between two intersections.

    >>> times_square = intersection(46, 7)
    >>> ess_a_bagel = intersection(51, 3)
    >>> taxicab(times_square, ess_a_bagel)
    9
    >>> taxicab(ess_a_bagel, times_square)
    9
    """
    "*** YOUR CODE HERE ***"

题目本身没有难度，主要培养的是我们分层设计的理念。在这题当中，taxicab函数当中输入的参数是两个intersection。并且给出了代码，通过intersection计算出对应的street和avenue。所以我们要做的就是调用这些方法，获取intersection的坐标，并遵循曼哈顿距离的方式进行计算。

def taxicab(a, b):
    """Return the taxicab distance between two intersections.
    """
    "*** YOUR CODE HERE ***"
    return abs(street(a) - street(b)) + abs(avenue(a) - avenue(b))

Q2: Squares only

给定一个整数序列，返回其中的完全平方数的完全平方根。

def squares(s):
    """Returns a new list containing square roots of the elements of the
    original list that are perfect squares.

    >>> seq = [8, 49, 8, 9, 2, 1, 100, 102]
    >>> squares(seq)
    [7, 3, 1, 10]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"

题目中提示我们可以使用round函数来做四舍五入：

>>> round(10.5)
10
>>> round(10.51)
11

做法很简单，我们对每个数开根号之后，再平方和原数进行比较，如果相等，说明该数是完全平方数，把答案纳入统计。

def squares(s):
    """Returns a new list containing square roots of the elements of the
    original list that are perfect squares.
    """
    "*** YOUR CODE HERE ***"
    import math
    def sqrt_root(x):
        return round(math.sqrt(x))
    return [sqrt_root(i) for i in s if sqrt_root(i) * sqrt_root(i) == i]

Q3: G function

假设G是一个数学函数，它的计算遵循以下计算逻辑：

G(n) = n,                                       if n <= 3
G(n) = G(n - 1) + 2 * G(n - 2) + 3 * G(n - 3),  if n > 3

现在需要我们分别使用递归和不使用递归实现G函数。

递归的版本很简单，base条件是n <= 3，当n大于3时，递归调用g(n-1), g(n-2), g(n-3)。

def g(n):
    """Return the value of G(n), computed recursively.

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'g', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"
    if n <= 3:
        return n
    return g(n-1) + 2 * g(n-2) + 3 * g(n-3)

迭代的做法类似，我们可以用变量维护

g_{n-1}, g_{n-2}, g_{n-3}

，每次通过公式计算出

g_n

。之后，我们再把

g_{n-1}, g_{n-2}, g_{n-3}

向右移动一位，让

g_{n-3}=g_{n-2}, g_{n-2} = g_{n-1}, g_{n-1}=g_n

def g_iter(n):
    """Return the value of G(n), computed iteratively.

    >>> g_iter(1)
    1
    >>> g_iter(2)
    2
    >>> g_iter(3)
    3
    >>> g_iter(4)
    10
    >>> g_iter(5)
    22
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'g_iter', ['Recursion'])
    True
    """
    "*** YOUR CODE HERE ***"
    if n <= 3:
        return n
    g_minus3, g_minus2, g_minus1 = 1, 2, 3
    for _ in range(4, n+1):
        g_next = g_minus1 + 2 * g_minus2 + 3 * g_minus3
        g_minus3, g_minus2, g_minus1 = g_minus2, g_minus1, g_next
    return g_minus1

Q4: Ping pong

乒乓序列是一段有升有降的序列：

1 2 3 4 5 6 [7] 6 5 4 3 2 1 [0] 1 2 [3] 2 1 0 [-1] 0 1 2 3 4 [5] [4] 5 6

对于第k个元素来说（k从1开始），如果它包含数字7，或者是7的倍数，那么它的升降顺序发生调转。所以我们可以看到上面序列当中第7、14、17、21、27、28……的位置升降状态发生了变化。

现在要实现一个pingpang函数，返回乒乓序列中第n个元素，并且不能使用任何赋值语句，可以使用def定义函数。

作业中为我们提供了一个工具函数has_seven，用来判断数字当中是否包含7。

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    if k % 10 == 7:
        return True
    elif k < 10:
        return False
    else:
        return has_seven(k // 10)

其实pingpong序列的逻辑并不复杂，我们使用循环很容易计算出答案，但题目当中要求了我们不能使用赋值语句，也就是说我们不能将中间结果存储下来，那么就只能通过递归，让解释器替我们去存储中间结果了。

我们很容易就写出结构：

def pingpong(n):
  if n <= 7:
     return n
  return pingpong(n-1) + diff(n)

也就是序列的前一个数加上这一次的改变量，pingpong函数我们有了，但diff还没有。所以我们还需要实现diff函数，diff函数也可以使用类似的思想：

def diff(n):
   if n < 7:
       return 1
    return diff(n-1) * (-1 if has_seven(n-1) or (n-1) % 7 == 0 else 1)

通过观察可以发现序号小于7的时候，每一次的变化量是1，之后每次遇到翻转变化量乘上-1，不翻转就保持不变，相当于乘上1。

我们把这两段代码合在一起，就得到答案了：

def pingpong(n):
    """Return the nth element of the ping-pong sequence.
    """
    "*** YOUR CODE HERE ***"
    if n <= 7:
        return n

    def diff(n):
        if n < 7:
            return 1
        return diff(n-1) * (-1 if has_seven(n-1) or (n-1) % 7 == 0 else 1)
        
    return pingpong(n-1) + diff(n)

Q5: Count change

有一个机器能够吐出面额为2的幂的硬币，比如1分、2分、4分、8分……

现在给定一个整数amount，请问机器吐出对应面值的硬币有多少种可能？

比如amount=7时一共有6种可能：

7个1
5个1和1个2
3个1,2个2
3个1,1个4
1个1，3个2
1个1,1个2,1个4

单纯地看本题，其实难度不低。但本次作业给了提示，可以参考之前的一题。

之前有一道类似的问题，给定两个整数n和m，要求将n拆分成若干个不大于m的整数的和，一共存在的可能数。

比如当n=6，m=4时，一共有9种可能：

6 = 2 + 4
6 = 1 + 1 + 4
6 = 3 + 3
6 = 1 + 2 + 3
6 = 1 + 1 + 1 + 3
6 = 2 + 2 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 1 + 1 + 1 + 1

这是怎么实现的呢？

对于每次拆分的时候，我们都有两种选择，拆分的结果当中存在m，一种是不存在。如果我们把m看成一种策略的话，就有两种可能，使用这个策略和不使用。

使用这个策略那么n会减去m，m不变，因为m可以使用任意多次。如果不使用m这个策略，则跳过，判断策略m-1，也就是说我们是假设策略是从大到小选择的。这样操作可以避免重复，比如先减1再减3和先减3再减1是一样的，但我们规定了从大到小之后，就只存在先减3再减1的可能了。

所以使用递归的话，其实很简单就可以得出答案，代码如下：

def count_partitions(n, m):
    """Count the ways to partition n using parts up to m."""
    if n == 0:
      return 1
    elif n < 0:
      return 0
    elif m == 0:
      return 0
    else:
      return count_partitions(n-m, m) + count_partitions(n, m-1)

我们仿照上面这题，采用同样的思路。首先我们找到不大于amount的最大策略m，然后从m开始递归。每一次也无非两种选择，使用m和不使用m。如果使用m，那么amount-m，如果不使用m，考虑m/2的策略。

由于原题当中只有一个输入，所以我们需要在函数内部定义另外一个函数：

def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** YOUR CODE HERE ***"
    import math
    def process(amount, upper):
        if amount == 0 or upper == 1:
            return 1
        if amount < 0:
            return 0
        return process(amount-upper, upper) + process(amount, upper // 2)
    return process(amount, pow(2, round(math.log2(amount))))

Q6: Anonymous factorial

本题为附加题，难度不小。

首先，我们可以使用匿名函数来进行递归，比如我们使用匿名函数来计算阶乘：

fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
fact(5)

虽然是使用了匿名函数，但是我们一样有函数名fact。现在希望我们可以实现一个函数，可以在完全没有函数名的情况下实现阶乘。

from operator import sub, mul

def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'make_anonymous_factorial', ['Assign', 'AugAssign', 'FunctionDef', 'Recursion'])
    True
    """
    return 'YOUR_EXPRESSION_HERE'

要求只能使用一行代码实现，并且实现当中不能使用赋值、函数定义和递归，也不能在return的语句当中调用make_anonymous_factorial函数。

拿到这样的题目，第一反应估计都是蒙圈，但冷静下来，其实是可以找到思路的。首先我们要做的是找到问题，我们现在不知道怎么实现，其实并不是遇到了实际的问题，最大的问题就是没有遇到实际问题本身。所以我们要先分析问题，找到其中的问题。

可以明确的是，根据样例，我们需要返回一个函数，那么我们肯定需要使用lambda关键字定义一个匿名函数进行返回。

我们可以试着写一下匿名函数：

return lambda x: 1 if x == 1 else mul(x, fact(x-1))

写一下就发现问题了，这里的fact函数并没有定义，并且这个没有定义的函数其实就是我们写的匿名函数本身。也就是说我们要在匿名函数里实现递归，让它能调用自己。

但题目当中限制了，我们不能使用赋值语句给它命名，我们不可能在不知道函数名字的情况下调用函数。所以到这里，难点才真正浮现出来。

其实这个问题是可以解决的，怎么解决呢？我们把fact函数作为参数传递进去，而不是直接通过名字获取：

return (lambda f: lambda x: if x == 1 else mul(x, f(x-1)))(f)

但是这本质上只是把递归的过程转移到了函数f身上，我们还是要实现一个可以递归的匿名函数f才行。既然f本身是一个递归函数，那么上面的代码其实也可以写成这样：

return (lambda f: lambda x: f(x))(f)

在上面的设想当中，f只有递归的逻辑，但实际上不是，f还需要知道x的取值，这样才能判断递归什么时候结束。所以x也必须要传入f当中，但这依然解决不了无法递归的问题。

这个问题才是本题的核心难点，解决它的关键就藏在题目给的样例里：

fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))

我们仔细看一下这行代码，就会发现这行代码本身就是非常混乱的。如果Python解析器是先执行完右侧的函数再来赋值给左边，那么右边的匿名函数在执行的时候，fact变量其实还没有绑定，而要绑定fact，就需要先执行完lambda语句，这样就构成了一个死循环。

所以我猜测，可能Python解释器虽然是先执行完右侧的语句再绑定，但在执行右侧之前，左侧的变量就已经先创建好了。并且在执行lambda的时候并不会执行严格的检查，只有这样，才不会陷入死循环。

这个fact其实是既作为参数又作为结果，我们就要利用这一点来解决问题，我们让我们的f也一样既是一个参数也是一个结果。

我们给f函数增加一个参数f，接收一个传入的函数，有了传入的函数就可以递归调用了，虽然这个函数就是它本身：

return (lambda f: lambda x: f(f, x))(lambda f, x: return 1 if x == 1 else mul(x, f(f, x-1)))

虽然只是Python基础语法的运用，但这里面绕了好几道弯，想要做出来，真不是一件容易的事情。

不禁让我感慨一句，真不愧是伯克利啊……

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 Coder梁微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度