vlambda博客
学习文章列表

- 课程大类AGENDA  -

01 Scratch 初中高

01 女性编程日周二

02 Python 编程思维

02 数字设计3D实践

03 VEX IQ 理论和实战

03 创客体验 免费预约

04 ACM/NOI 算法

04 物联网基础实践

▽  课程体系和进度 ▽    

丁丁猫python起跑班课程内容覆盖7个大模块，每个模块文末详细技能知识点。3个班的进度相同但讲的深度不同。 课程设计中将感受到对逻辑课的高度重视，弥补国内K12编程和数学课程缺少的重要一环。

This browser does not support music or audio playback. Please play it in Weixin or another browser.

注意：下面的所有代码都是用Python 3.8.12测试的，有些语法可能与旧版本不兼容。本文以最小的代价掌握 Python中的递归，办法是常见的小任务改用递归重写

任何函数式编程语言的主要卖点之一是递归，或者说，你可以用一种优雅的方式来实现递归函数的语法。在这篇文章中，我想说明Python可以很容易地适应以函数式方式编写，证明它是一种真正的多范式语言。

每个人都知道使用斐波那契数列的递归的经典例子，所以让我们看看它的相应的Python代码。

def fib(n: int) -> int:
 if n == 0 or n == 1: # base case
 return n

 return fib(n-2) + fib(n-1)

我们有一个接受数字并返回该数字对应的斐波那契数列元素的函数。每个递归函数都应该有一个基本情况（也被称为边缘情况），本质上它是一个代码分支，在不进行任何后续递归调用的情况下立即停止或返回一些东西。

然后，我们有两个递归函数调用，计算序列中的两个先前的数字，基本上这与定义相对应，每个数字只是一个序列中两个先前数字的总和。

大多数函数式语言也是已知的静态类型，所以我们也在我们的代码示例中使用类型注释，使它们看起来更像函数式。

最小的努力掌握递归

现在让我们来实现几个常用的函数，以说明这种东西可以用递归的方式简洁地实现。我们的第一个主题是最大/最小函数，从列表中返回目标元素。

def maximum(arr):
 if not arr:
 raise ValueError('Cannot find maximum in an empty list')

 if len(arr) == 1:
 return arr[0]

 x, *tail = arr
 max_tail = maximum(tail)
 return x if x > max_tail else max_tail

通常我们从一个基本情况开始，知道只包含一个元素的列表的最大元素是该元素本身。整个列表中最大的元素要么是当前元素，要么是序列其他部分的最大元素。在这里，我们使用列表解构来无缝地从列表中提取第一个元素以及它的尾部进入两个不同的变量。

同样的结果也可以用下面的方法完成（如果你对这样的语法不适应的话）。

 
   
   
 

  
    
    
  arr = [1, 2, 3, 4]
x, tail = arr.pop(0), arr
# (1, [2, 3, 4])
Another option is to use slices on the list:

arr = [1, 2, 3, 4]
x, tail = arr[0], arr[1:]
# (1, [2, 3, 4])

arr = [1, 2, 3, 4] 。
x, tail = arr.pop(0), arr
# (1, [2, 3, 4])
另一个选择是在列表上使用片断。

arr = [1, 2, 3, 4].
x, tail = arr[0], arr[1:]
# (1, [2, 3, 4])


 
   
   
 

同样的逻辑也适用于最小函数，但这里我们不使用比较法，而是调用min内置函数。

from typing import List

def minimum(arr: List[int]) -> int: # type annotations for clarity
 x, *tail = arr # list unpacking
 if not tail: # base case
 return x

 return min(x, minimum(tail)) # recursive call

用递归重写一切

下面你可以找到几个额外的函数，只是为了证明它们的结构是多么的相似，以及任何结构都可以流畅地转化为递归调用。

replicate 接收一个数字 n 和一个值 val，并返回一个包含相同 val 值的 n 个副本的列表

def replicate(n, val):
 if n <= 0:
 return []

 return [val, *replicate(n-1, val)]
Example invocation:

>>> replicate(3, 42)
[42, 42, 42]

take - 给定一个数字n和一个列表arr，返回该列表中的前n个元素

def take(n, arr):
 if n <= 0 or not arr:
 return []

 x, *tail = arr
 return [x, *take(n-1, tail)]


>>> take(3, [0, 1, 2, 3, 4])
[0, 1, 2]
>> take(5, [])
[]

elem - 对于提供的值val和一个列表arr，它返回一个列表是否包含该元素

def elem(val, arr) -> bool:
 if not arr:
 return False

 x, *tail = arr
 if val == x:
 return True
 return elem(val, tail)

#Example invocation:

>>> arr1 = [1, 2, 3]
>>> arr2 = ['a', 'b', 'c', 'd']
>>> elem(0, arr1)
False
>>> elem('d', arr2))
True

反转：只是简单地将一个列表反转

def reverse(arr):
 if not arr:
 return []

 x, *tail = arr
 return [*reverse(tail), x]
Example invocation:

>>> reverse([1, 2, 3, 4, 5])
[5, 4, 3, 2, 1]
>>> reverse([])
[]

zip接收两个列表并将它们压缩在一起。

它返回一个列表，每个元素都是输入列表中的一对匹配元素。如果一个列表较短，则返回的列表不会包含较长列表中与任何内容不匹配的项目。

例子调用（结果列表不包含d元素，因为它不与第一个列表中的任何内容匹配）。

def zip(xs, ys):
 if not xs or not ys:
 return []

 x, *x_tail = xs
 y, *y_tail = ys
 return [(x, y), *zip(x_tail, y_tail)]

>> arr1 = [1, 2, 3]。
>> arr2 = ['a', 'b', 'c', 'd'] 
>> zip(arr1, arr2)
[(1, 'a'), (2, 'b'), (3, 'c')] 

作为额外的练习，你可以从itertools模块的任何一个函数开始，并尝试想出等效的递归代码。那里的大多数函数都在上面的文档页面中提供了粗略的代码实现，所以会更容易理解你要实现什么样的逻辑。

快排序

有很多图的遍历算法，使用递归函数以及这个quicksort算法的例子更容易实现，因为它们本身的定义是用递归术语声明的。为了完成排序，我们从枢轴元素开始，在最简单的情况下，枢轴元素只是我们列表中的第一个元素，然后把它放在两个分区之间：第一个分区是小于或等于枢轴的排序元素数组，第二个分区是大于枢轴的排序元素数组。

def quicksort(arr):
 if not arr:
 return []
 x, *tail = arr
 smaller_sorted = quicksort([t for t in tail if t <= x])
 bigger_sorted = quicksort([t for t in tail if t > x])
 return [*smaller_sorted, x, *bigger_sorted]

正如你所看到的，递归并不复杂，有些实现甚至可以比迭代式的实现更简单。有时，递归代码可能有点难以调试，所以当有疑问时，总是坚持使用对你来说更容易理解和维护的解决方案。否则，请继续使用递归函数实现你的新功能。编码愉快！

更多递归的文章>>

项目任务的递归>>

 1. Collections: 

List, Dictionary, Set, Tuple, Range, Enumerate, Iterator, Generator .

 2. Types:  

Type, String, Regular_Exp, Format, Numbers, Combinatorics, Datetime

 3. Syntax:   

Args, Inline, Closure, Decorator, Class, Duck_Types, Enum, Exceptions

 4. System:  

Print, Input, Command_Line_Arguments, Open, Path, Command_Execution.

 5. Data:  

CSV, JSON, Pickle, SQLite, Bytes, Struct, Array, MemoryView, D

编程营

To-Do Sept

 **ARDUINO - 2021年5月17日项目课程近期发布

大喵老师的任务式python课和数学物理一起搞！

秋季及寒假初中级混班项目制

 任务式学习课题一  糖纸换糖案例 学习循环控制 1 节课

形式：数学解法与编程思路对照；糖纸换糖的升级版叠乒乓球

技能点：while循环；字典；数据结构

Collections: List, Dictionary,loop

 

任务式学习课题二  银行利率的奥秘案例 学习变量赋值 1 节课

形式：自然数e；利率计算；代码；

技能点：变量赋值，while循环；数据机构

Collections: List, Range, Enumerate

 

任务式学习课题三  恺撒密码 2 节课

形式：分组加解密游戏；密码原理；高效代码；

技能知识点：for循环；切片，地址下标，ascii码；可视化plot

Collections: List, Range, Enumerate，string  

Libraries:Progress_Bar, Plot, Table

 

任务式学习课题四  高级函数专题 3节课

形式：高级函数的效率比较

技能知识点：Python高级函数：初学者容易忽视的利器

Collections，

 

任务式学习课题五  概率问题汇总  数学和编程 3 节课

形式：6个筛子一起扔和一个个掷比较；随机密码生成；火星机器人漫游

数学基础：概率知识；

技能知识点：for循环，生成随机数，数据结构

Collections: List, Range, Random，math

 

**每周编程角讨论的编程思想课题

暴力枚举的优化Make Decision : 决策树

Think with Graphs：图形思维

Parallelism：并行任务

Oder and Search：排序索引

Resource Tradeoffs：资源均衡

Abtraction ：抽象

Interface：接口

 

任务式学习课题六  智能合约房屋产权 1 节课

形式：模拟产权交易；

数学基础：布尔运算；

技能知识点：Bool运算符

Data: bool

 

任务式学习课题七  递归思想  数学和编程 3 节课

形式：斐波那契；汉诺塔；金字塔；

递归思想：概率知识；

技能知识点：for循环，生成随机数，数据结构

 

任务式学习课题六

搭建邮件服务器、爬虫、独立博客 3 节课

PIP管理python库更新下载；

Minecraft服务器；

形式：Python库；抓取喜欢的歌曲；建立自己的博客；

注册Github，codewars

丁丁猫亲子创客

计 算机编程 | VEX机器人 | 物联网

智能硬件 | 3D打印

NOIP竞赛

办公地址

源著天街写字楼20栋8-13

上课地点

鸿恩寺校区：江北鸿恩寺保利江上明珠锦园一栋4-15

金科十年城校区：江北区石马河金科十年城56栋10-2

合作示范授课校区

两江春城校区：渝北区余溪路63-1小树苗乐学中心

晶郦馆校区：江北新南路163号水晶郦城A馆三楼

九街校区：江北区洋河东路1号揽胜国际广场2楼