Homework 3: Recursion, Tree Recursion
Instructions
下载 hw03.zip。在存档中，您将找到一个名为 hw03.py 的文件，以及 ok 自动评分器的副本。
如果官方链接失效，你也可以通过我的 github 仓库 CS61A_Fall2024来获取我的代码。
重要
请注意，该代码包含答案，因此如果你想独立完成请务必提前将 hw03.py 中的答案删除！
提交：完成后，通过将您编辑的所有代码文件上传到 Gradescope 来提交作业。您可以在截止日期前多次提交；只有最后一次提交才会被评分。检查您是否已成功在 Gradescope 上提交了代码。有关提交作业的更多说明，请参阅实验 0。
使用 Ok：如果您对使用 Ok 有任何疑问，请参阅本指南。
阅读：您可能会发现以下参考资料很有用：
第 1.7 节 评分：作业根据正确性进行评分。每个错误的问题都会使总分减少一分。这项作业满分为 2 分。
Required Questions
Q1: Num Eights
编写一个递归函数 num_eights ，它接受一个正整数 n 并返回数字 8 在 n 中出现的次数。
提示
使用递归；如果使用任何赋值语句或循环，测试将失败。（您可以定义新函数，但也不要在其中放置赋值语句。）
def num_eights(n):
"""Returns the number of times 8 appears as a digit of n.
>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> num_eights(8782089)
3
>>> from construct_check import check
>>> # ban all assignment statements
>>> check(HW_SOURCE_FILE, 'num_eights',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q num_eights点击查看答案
def num_eights(n):
"""Returns the number of times 8 appears as a digit of n.
>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> num_eights(8782089)
3
>>> from construct_check import check
>>> # ban all assignment statements
>>> check(HW_SOURCE_FILE, 'num_eights',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
if n == 0:
return 0
else:
return (1 if n % 10 == 8 else 0) + num_eights(n // 10)Q2: Digit Distance
对于给定的整数，数字距离是连续数字之间绝对差的总和。例如：
61的数字距离为5，因为6 - 1的绝对值为5。71253的数字距离为12(abs(7-1) + abs(1-2) + abs(2-5) + abs(5-3)=6 + 1 + 3 + 2) 。6的数字距离为0，因为没有连续数字对。 编写一个函数来确定正整数的数字距离。您必须使用递归，否则测试将失败。
def digit_distance(n):
"""Determines the digit distance of n.
>>> digit_distance(3)
0
>>> digit_distance(777) # 0 + 0
0
>>> digit_distance(314) # 2 + 3
5
>>> digit_distance(31415926535) # 2 + 3 + 3 + 4 + ... + 2
32
>>> digit_distance(3464660003) # 1 + 2 + 2 + 2 + ... + 3
16
>>> from construct_check import check
>>> # ban all loops
>>> check(HW_SOURCE_FILE, 'digit_distance',
... ['For', 'While'])
True
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q digit_distance点击查看答案
def digit_distance(n):
"""Determines the digit distance of n.
>>> digit_distance(3)
0
>>> digit_distance(777) # 0 + 0
0
>>> digit_distance(314) # 2 + 3
5
>>> digit_distance(31415926535) # 2 + 3 + 3 + 4 + ... + 2
32
>>> digit_distance(3464660003) # 1 + 2 + 2 + 2 + ... + 3
16
>>> from construct_check import check
>>> # ban all loops
>>> check(HW_SOURCE_FILE, 'digit_distance',
... ['For', 'While'])
True
"""
"*** YOUR CODE HERE ***"
if n < 10:
return 0
else:
return abs(n % 10 - n // 10 % 10) + digit_distance(n // 10)Q3: Interleaved Sum
编写一个函数 interleaved_sum ，该函数接受一个数字 n 和两个单参数函数： odd_func 和 even_func 。它将 odd_func 应用于每个奇数，将 even_func 应用于从 1 到 n （含）的每个偶数，并返回总和。
例如，执行 interleaved_sum(5, lambda x: x, lambda x: x * x) 返回 1 + 2*2 + 3 + 4*4 + 5 = 29 。
重要
实现此函数时，请勿使用任何循环或直接测试数字是奇数还是偶数（不使用 % ）。不要直接检查数字是偶数还是奇数，而是从 1 开始，因为您知道 1 是奇数。
提示
引入一个内部辅助函数，该函数接受奇数 k 并计算从 k 到 n （包括 n ）的交错和。
def interleaved_sum(n, odd_func, even_func):
"""Compute the sum odd_func(1) + even_func(2) + odd_func(3) + ..., up
to n.
>>> identity = lambda x: x
>>> square = lambda x: x * x
>>> triple = lambda x: x * 3
>>> interleaved_sum(5, identity, square) # 1 + 2*2 + 3 + 4*4 + 5
29
>>> interleaved_sum(5, square, identity) # 1*1 + 2 + 3*3 + 4 + 5*5
41
>>> interleaved_sum(4, triple, square) # 1*3 + 2*2 + 3*3 + 4*4
32
>>> interleaved_sum(4, square, triple) # 1*1 + 2*3 + 3*3 + 4*3
28
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
True
>>> check(HW_SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are
True
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q interleaved_sum点击查看答案
def interleaved_sum(n, odd_func, even_func):
"""Compute the sum odd_func(1) + even_func(2) + odd_func(3) + ..., up
to n.
>>> identity = lambda x: x
>>> square = lambda x: x * x
>>> triple = lambda x: x * 3
>>> interleaved_sum(5, identity, square) # 1 + 2*2 + 3 + 4*4 + 5
29
>>> interleaved_sum(5, square, identity) # 1*1 + 2 + 3*3 + 4 + 5*5
41
>>> interleaved_sum(4, triple, square) # 1*3 + 2*2 + 3*3 + 4*4
32
>>> interleaved_sum(4, square, triple) # 1*1 + 2*3 + 3*3 + 4*3
28
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
True
>>> check(HW_SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are
True
"""
"*** YOUR CODE HERE ***"
def helper(i, is_odd):
if i > n:
return 0
if is_odd:
return odd_func(i) + helper(i+1, False)
else:
return even_func(i) + helper(i+1, True)
return helper(1, True)Q4: Count Dollars
给定一个正整数 total ，如果美元钞票的总价值为 total ，则一组美元钞票会为 total 找零。这里我们将使用标准的美元钞票面值：1、5、10、20、50 和 100。例如，以下集合会为 15 找零：
15 张 1 美元钞票
10 张 1 美元钞票，1 张 5 美元钞票
5 张 1 美元钞票，2 张 5 美元钞票
5 张 1 美元钞票，1 张 10 美元钞票
3 张 5 美元钞票
1 张 5 美元钞票，1 张 10 美元钞票
因此，有 6 种方法可以找零 15 。编写一个递归函数 count_dollars ，它接受一个正整数 total ，并返回使用 1、5、10、20、50 和 100 美元钞票为 total 找零的方法数。
在您的解决方案中使用 next_smaller_dollar ： next_smaller_dollar 将返回输入中下一个较小的美元钞票面值（例如 next_smaller_dollar(5) 为 1 ）。如果下一个美元钞票面值不存在，该函数将返回 None 。
重要
使用递归：如果使用循环，测试将失败。
提示
请参阅 count_partitions 的实现，以了解如何计算使用较小部分得出最终值的方法。如果您需要在递归调用中跟踪多个值，请考虑编写辅助函数。
def next_smaller_dollar(bill):
"""Returns the next smaller bill in order."""
if bill == 100:
return 50
if bill == 50:
return 20
if bill == 20:
return 10
elif bill == 10:
return 5
elif bill == 5:
return 1
def count_dollars(total):
"""Return the number of ways to make change.
>>> count_dollars(15) # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
6
>>> count_dollars(10) # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
4
>>> count_dollars(20) # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
10
>>> count_dollars(45) # How many ways to make change for 45 dollars?
44
>>> count_dollars(100) # How many ways to make change for 100 dollars?
344
>>> count_dollars(200) # How many ways to make change for 200 dollars?
3274
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_dollars', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q count_dollars点击查看答案
def next_smaller_dollar(bill):
"""Returns the next smaller bill in order."""
if bill == 100:
return 50
if bill == 50:
return 20
if bill == 20:
return 10
elif bill == 10:
return 5
elif bill == 5:
return 1
def count_dollars(total):
"""Return the number of ways to make change.
>>> count_dollars(15) # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
6
>>> count_dollars(10) # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
4
>>> count_dollars(20) # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
10
>>> count_dollars(45) # How many ways to make change for 45 dollars?
44
>>> count_dollars(100) # How many ways to make change for 100 dollars?
344
>>> count_dollars(200) # How many ways to make change for 200 dollars?
3274
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_dollars', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
def helper(total, bill):
if total == 0:
return 1
elif bill == 1:
return 1
elif total < bill:
return helper(total, next_smaller_dollar(bill))
elif total >= bill:
return helper(total - bill, bill) + helper(total, next_smaller_dollar(bill))
return helper(total, 100)Check Your Score Locally
您可以通过运行来在本地检查此作业的每个问题的分数：
python ok --score我的得分：
PS D:\Github\CS61A_Fall2024\hw\hw03> python ok --score
=====================================================================
Assignment: Homework 3
OK, version v1.18.1
=====================================================================
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Scoring tests
---------------------------------------------------------------------
Doctests for num_eights
>>> from hw03 import *
>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> num_eights(8782089)
3
>>> from construct_check import check
>>> # ban all assignment statements
>>> check(HW_SOURCE_FILE, 'num_eights',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True
Score: 1.0/1
---------------------------------------------------------------------
Doctests for digit_distance
>>> from hw03 import *
>>> digit_distance(3)
0
>>> digit_distance(777) # 0 + 0
0
>>> digit_distance(314) # 2 + 3
5
>>> digit_distance(31415926535) # 2 + 3 + 3 + 4 + ... + 2
32
>>> digit_distance(3464660003) # 1 + 2 + 2 + 2 + ... + 3
16
>>> from construct_check import check
>>> # ban all loops
>>> check(HW_SOURCE_FILE, 'digit_distance',
... ['For', 'While'])
True
Score: 1.0/1
---------------------------------------------------------------------
Doctests for interleaved_sum
>>> from hw03 import *
>>> identity = lambda x: x
>>> square = lambda x: x * x
>>> triple = lambda x: x * 3
>>> interleaved_sum(5, identity, square) # 1 + 2*2 + 3 + 4*4 + 5
29
>>> interleaved_sum(5, square, identity) # 1*1 + 2 + 3*3 + 4 + 5*5
41
>>> interleaved_sum(4, triple, square) # 1*3 + 2*2 + 3*3 + 4*4
32
>>> interleaved_sum(4, square, triple) # 1*1 + 2*3 + 3*3 + 4*3
28
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
True
>>> check(HW_SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are
True
Score: 1.0/1
---------------------------------------------------------------------
Doctests for count_dollars
>>> from hw03 import *
>>> count_dollars(15) # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
6
>>> count_dollars(10) # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
4
>>> count_dollars(20) # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
10
>>> count_dollars(45) # How many ways to make change for 45 dollars?
44
>>> count_dollars(100) # How many ways to make change for 100 dollars?
344
>>> count_dollars(200) # How many ways to make change for 200 dollars?
3274
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_dollars', ['While', 'For'])
True
Score: 1.0/1
---------------------------------------------------------------------
Point breakdown
num_eights: 1.0/1
digit_distance: 1.0/1
interleaved_sum: 1.0/1
count_dollars: 1.0/1
Score:
Total: 4.0
Backup... 100% complete
Backup past deadline by 172 days, 19 hours, 9 minutes, and 29 seconds
Backup successful for user: zhiyong947@gmail.com
URL: https://okpy.org/cal/cs61a/fa24/hw03/backups/p7ZGAN
OK is up to date
PS D:\Github\CS61A_Fall2024\hw\hw03>这不会提交作业！当您对分数满意时，请将作业提交给 Gradescope 以获得学分。
Optional Questions
这些问题是可选的。如果您不完成它们，您仍将获得此作业的学分。它们是很好的练习，所以无论如何都要完成它们！
Q5: Count Dollars Upward
编写一个递归函数 count_dollars_upward ，它与 count_dollars 类似，只是它使用 next_larger_dollar ，它从输入中返回下一个更大的美元钞票面值（例如 next_larger_dollar(5) 为 10 ）。如果下一个美元钞票面值不存在，该函数将返回 None 。
重要
使用递归；如果使用循环，测试将失败。
def next_larger_dollar(bill):
"""Returns the next larger bill in order."""
if bill == 1:
return 5
elif bill == 5:
return 10
elif bill == 10:
return 20
elif bill == 20:
return 50
elif bill == 50:
return 100
def count_dollars_upward(total):
"""Return the number of ways to make change using bills.
>>> count_dollars_upward(15) # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
6
>>> count_dollars_upward(10) # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
4
>>> count_dollars_upward(20) # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
10
>>> count_dollars_upward(45) # How many ways to make change for 45 dollars?
44
>>> count_dollars_upward(100) # How many ways to make change for 100 dollars?
344
>>> count_dollars_upward(200) # How many ways to make change for 200 dollars?
3274
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_dollars_upward', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q count_dollars_upward点击查看答案
def next_larger_dollar(bill):
"""Returns the next larger bill in order."""
if bill == 1:
return 5
elif bill == 5:
return 10
elif bill == 10:
return 20
elif bill == 20:
return 50
elif bill == 50:
return 100
def count_dollars_upward(total):
"""Return the number of ways to make change using bills.
>>> count_dollars_upward(15) # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
6
>>> count_dollars_upward(10) # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
4
>>> count_dollars_upward(20) # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
10
>>> count_dollars_upward(45) # How many ways to make change for 45 dollars?
44
>>> count_dollars_upward(100) # How many ways to make change for 100 dollars?
344
>>> count_dollars_upward(200) # How many ways to make change for 200 dollars?
3274
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_dollars_upward', ['While', 'For'])
True
"""
"*** YOUR CODE HERE ***"
def helper(total, bill):
if total == 0:
return 1
elif total < 0:
return 0
elif next_larger_dollar(bill):
return helper(total - bill, bill) + helper(total, next_larger_dollar(bill))
else:
return helper(total - bill, bill)
return helper(total, 1)Just For Fun Questions
以下问题超出了 61A 的范围。如果您想要额外的挑战，可以尝试这些问题，但它们只是课程不需要的谜题。几乎所有学生都会跳过它们，这没关系。
Q6: Towers of Hanoi
汉诺塔是经典的拼图游戏，由三根杆和一些大小各异的圆盘组成，这些圆盘可以滑到任何杆上。拼图游戏从 start 杆上整齐地堆叠的 n 个圆盘开始，按大小从大到小的顺序排列，最小的圆盘放在顶部，形成一个圆锥形。
谜题的目标是将整个堆栈移动到 end 杆，遵循以下规则：
- 一次只能移动一个圆盘。
- 每次移动包括从一根杆上取下顶部（最小）圆盘并将其滑到另一根杆上，该杆上可能已经存在其他圆盘。
- 任何圆盘都不能放在较小的圆盘上。 完成
move_stack的定义，该定义打印出将n个圆盘从 start 杆移动到 end 杆而不违反规则所需的步骤。提供的print_move函数将打印出将单个圆盘从给定origin移动到给定destination的步骤。
提示
在一张纸上画出几个带有不同 n 的游戏，并尝试找到适用于任何 n 的圆盘移动模式。在您的解决方案中，每当您需要将少于 n 的任意数量的圆盘从一个杆移动到另一个杆时，请采取递归的飞跃。如果您需要更多帮助，请参阅以下提示。
汉诺塔中使用的策略是将除底部圆盘之外的所有圆盘移到第二个柱子上，然后将底部圆盘移到第三个柱子上，然后将除第二个圆盘之外的所有圆盘从第二个柱子移到第三个柱子上。
您不需要担心的一件事是收集所有步骤。只要您确保按顺序打印移动，print 就可以有效地“收集”终端中的所有结果。
def print_move(origin, destination):
"""Print instructions to move a disk."""
print("Move the top disk from rod", origin, "to rod", destination)
def move_stack(n, start, end):
"""Print the moves required to move n disks on the start pole to the end
pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
"*** YOUR CODE HERE ***"使用 Ok 来测试你的代码：
python ok -q move_stack点击查看答案
def print_move(origin, destination):
"""Print instructions to move a disk."""
print("Move the top disk from rod", origin, "to rod", destination)
def move_stack(n, start, end):
"""Print the moves required to move n disks on the start pole to the end
pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
"*** YOUR CODE HERE ***"
if n == 1:
print_move(start, end)
else:
temp = 6 - end - start
move_stack(n-1, start, temp)
print_move(start, end)
move_stack(n-1, temp, end)Q7: Anonymous Factorial
这个问题表明，可以编写递归函数而不在全局框架中为其指定名称。
可以使用条件表达式将递归阶乘函数写为单个表达式。
>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120但是，此实现依赖于事实（无双关语意）的事实，即 fact 有一个名称，我们在 fact 主体中引用该名称。要编写递归函数，我们始终使用 def 或赋值语句为其命名，以便我们可以在其自身主体中引用该函数。在这个问题中，您的工作是递归定义 fact 而不为其命名！
编写一个仅使用调用表达式、条件表达式和 lambda 表达式（无赋值或 def 语句）计算 n 阶乘的表达式。
提示
注意：您不能在返回表达式中使用 make_anonymous_factorial 。
operator 模块中的 sub 和 mul 函数是解决此问题所需的唯一内置函数。
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
>>> # ban any assignments or recursion
>>> check(HW_SOURCE_FILE, 'make_anonymous_factorial',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'FunctionDef', 'Recursion'])
True
"""
return 'YOUR_EXPRESSION_HERE'使用 Ok 来测试你的代码：
python ok -q make_anonymous_factorial点击查看答案
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
>>> # ban any assignments or recursion
>>> check(HW_SOURCE_FILE, 'make_anonymous_factorial',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'FunctionDef', 'Recursion'])
True
"""
return (lambda f: f(f))(
lambda f: lambda n: 1 if n == 1 else mul(n, f(f)(sub(n, 1)))
)