空间复杂度：用来评估算法内存占用大小的式子
空间复杂度的表示方式与时间复杂度完全一样
算法使用了几个变量：O(1)
算法使用了长度为n的一维列表：O(n)
算法使用了长度为m行n列的二维列表：O(mn)
递归
递归的两个特点：
1、调用自身
2、结束条件
举例：
def func1(x):
print(x)
func1(x-1)
不是合法的递归，例如，代入x=3，会无限执行下去，没有结束条件；是一个死递归
def func2(x):
if x>0:
print(x)
func2(x+1)
不是合法的递归，看似有结束条件x>0，即当x<=0时结束，x+1会永远大于0，依然不会结束，故相当于没有结束条件
例如，代入x=3，会打印4、5、6、7…，而不会到<0结束
def func3(x):
if x>0:
print(x)
func3(x-1)
是合法的递归，func3先打印，再执行函数；例如，代入x=3，会打印3、2、1
示意图如下：先打印，再递归
外框表示函数的执行，窄框表示打印，长框表示又进入一个函数的调用（递归），蓝线表示函数执行的过程，从上到下
def func4(x):
if x>0:
func4(x – 1)
print(x)
是合法的递归，func4先执行函数，再打印；例如，代入x=3，会打印1、2、3
示意图如下：先递归，再打印
外框表示函数的执行，长框表示先进入一个函数的调用（递归），窄框表示打印，蓝色箭头表示函数执行的过程，从上到下