16.1-函数递归
每个人的一生,都有自己必须要吃的苦,总要经受一些磨砺,才能靠近自己期待的生活。人，除了自渡，他人爱莫能助！所以无论生活多难，你都要坚持勇敢。
函数递归有性能问题，但非常绕，一般是面试的考点^，重点题目！**
递归函数即直接或间接调用自身的函数，且递归过程中必须有一个明确的递归结束条件，称为递归出口。递归极其强大一点就是能够遍历任意的，不可预知的程序的结构，比如遍历复杂的嵌套列表。
本章总结：
- 计算机数据结构常见的还有：栈、队列、堆、链表、树、图 等；这些数据结构广泛应用在计算机编程的各个方面。 栈的特点 后进先出；，栈跟线程相关；栈是每个线程自己的数据结构；
- 堆（heap）是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：堆是受GC管理的；
栈 (Stack)：是一种只能通过访问其一端来实现数据存储与检索的线性数据结构，具有后进先出 ( last in first out，LIFO ) 的特征；只能在栈的一端进行插入和删除运算，这一端被称为栈顶，另一端称为栈底；先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。将数据压入栈顶，称为入栈（push）；将数据从栈顶取出，称为出栈（pop）。
在栈的设计中，主要需要：栈顶元素 top、入栈 push 方法、出栈 pop 方法、获取栈顶元素 peek ;
压栈：递归效率不高，可能会导致栈溢出(函数调用是通过栈这种数据结构实现的，每进入一个函数调用，栈就会增加一层栈帧，函数每返回，栈就会减少一层栈帧，由于栈的大小不是无限的，递归调用过多，可能会导致栈溢出)
Cpython 递归深度（压栈）限制1000 ；
总结
1.压栈 类似如 压上头、放作业本一层一层往上叠，是引用类型；函数结束后，清除函数的层数；
2.栈是跟线程相关，栈是每个线程自己的数据结构；
栈跟线程相关
def fn(n):
print(n)
fn(1) # 线程1
fn(2) # 线程2
fn('a')
---------------------------------------------
1
2
a
1.可变类型列表要区别对待 ；
def fn(n=[]):
n += [1] #覆盖原来的 extend;
def fn1(n=[]):
n = n + [1] # new list
Rscursion 递归
当边界条件不满足的时候，递归前进；
当边界条件满足的时候，递归返回；
递归函数优点
递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。
递归函数缺点
递归调用的次数过多，会导致栈溢出。还是用之前阶乘的例子，1000 的阶乘用递归函数会报错。
练习1：fib数列问题；
写法1： fib序列；
a = 0
b = 1
n = 4
for i in range(n):
a,b = b, a+b
print(b)
-------------------------------
1
2
3
5
写法2：用函数递归；性能极差； fib(n) = fib(n-1) + fib(n-2)
def fib(n):
if n < 3:
return 1
else:
return fib(n-1) + fib(n-2)
for i in range(1,11):
print(fib(i))
写法3：三元表达式
def fib(n):
return 1 if n<3 else fib(n-1)+fib(n-2)
fib(4)
写法4：函数调用 优化策略 —— 函数递归变成for循环；
def fib(n,pre=0,cur=1):
pre,cur = cur,pre + cur
if n == 0:
return pre
return fib(n-1,pre,cur)
fib(3)
-----------------
3
循环递归调用是非常危险的；往往挖这种情况发上在代码复杂的情况下；
函数递归总结：
1.递归是一种很自然的表达，符合逻辑要求；
2.递归相对运行效率低，第一次调用函数都要开辟栈帧；
3.递归有深度限制，注意栈，内存是否溢出；
4.如果有限次数的递归，可以使用循坏代替；注意是否出现死循环；
5.即是递归代码简洁，但是能不用就不用递归；
