1、函数执行流程：
def foo1(a, a1=1): print("foo1 called", a, a1) def foo2(b): foo3(b) print("foo2 called", b) def foo3(c): print("foo3 called", c) def main(): print("main called") foo1(100, 101) foo2(200) print("main ending") main() # 函数执行流程： 1.全局帧中生成 foo1、foo2、foo3、main 函数对象； 2.main 函数调用； 3.main 中查找内建函数 print 压栈，将常量字符串压栈，调用函数，弹出栈顶； 4.main 中全局查找函数 foo1 压栈，将常量 100、101 压栈，调用函数 foo1，创建栈帧。print 函数压栈，字符串和变量 a、a1 压栈，调用函数，弹出栈顶，返回值； 5.main 中全局查找 foo2 函数压栈，将常量 200 压栈，调用 foo2，创建栈帧。foo3 函数压栈，变量 b 引用压栈，调用 foo3，创建栈帧。foo3 完成 print 函数调用后返回。foo2 恢复调用，执行 print 后，返回值。main 中 foo2 调用结束弹出栈顶，main 继续执行 print 函数，弹出栈顶，main 函数返回。
def foo(a): print('foo') def main(): print('main start') foo([]) # 在内存中即堆中开辟一个列表，压栈地址，弹出 foo([]) # 在堆中再开辟一个列表，压栈地址，弹出 print('main ending') main() def foo1(a): print('foo1') def main(): print('main start') lst = [] # 先在堆中开辟一个列表，压栈 foo1(lst) # 引用地址，弹出，列表不消亡 foo1(lst) # 再引用地址 print('main ending') main()
2、递归 Recursion
函数直接或者间接调用自身就是递归
递归需要有边界条件、递归前进段、递归返回段
递归一定要有边界条件
当边界条件不满足的时候， 递归前进；当边界条件满足的时候，递归返回
import sys print(sys.getrecursionlimit()) # cpython 对递归调用的深度做了限制，限制 1000 下调用 def foo1(): foo1() foo1() # 最大递归深度(函数栈太大)限制，报错
例：斐波那契数列 Fibonacci number：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
如果设 F(n) 为该数列的第n项 (n∈N*)，那么这句话可以写成如下形式：F(n)=F(n-1)+F(n-2)
F(0)=0, F(1)=1, F(n)=F(n-1)+ F(n-2)
# 循环实现 a, b = 0, 1 for i in range(35): a, b = b, a+b print(a) # 递归实现 def fib(n): # 函数调用特别多，一层一层 if n < 3: # 定义边界 return 1 return fib(n-1) + fib(n-2) print(fib(4)) def fib1(n): return 1 if n < 3 else fib(n-1) + fib(n-2) print(fib(4)) # 递归解析：层层解析，循环计算，效率低下
fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) fib(3) = fib(2) + fib(1)
递归要求：
递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用
递归调用的深度不宜过深
Python 对递归调用的深度做了限制，以保护解释器
超过递归深度限制，抛出 RecursionError: maxinum recursion depth exceeded 超出最大深度
sys.getrecursionlimit()，查看最大深度
递归的性能：
循环稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果。
fib 函数代码极简易懂，但是只能获取到最外层的函数调用，内部递归结果都是中间结果。而且给定一个 n 都要进行近 2n 次递归，深度越深，效率越低。为了获取斐波那契数列需要外面再套一个 n 次的循环，效率就更低了。
递归还有深度限制，如果递归复杂，函数反复压栈，栈内存很快就溢出了。
思考：这个极简的递归代码能否提高性能呢?
# 函数调用模拟循环 def fib(n, a=0, b=1): a, b = b, a + b if n == 1: return a return fib(n-1, a, b) print(fib(4))
间接递归，是通过别的函数调用了函数自身
def foo1(): foo2() def foo2(): foo1()
但是，如果构成了循环递归调用是非常危险的，但是往往这种情况在代码复杂的情况下，还是可能发生这种调用。要用代码的规范来避免这种递归调用的发生。
递归总结：
递归是一种很自然的表达，符合逻辑思维；
递归相对运行效率低，每一次调用函数都要开辟栈帧；
递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了；
如果是有限次数的递归，可以使用递归调用，或者使用循环代替，循环代码稍微复杂一些， 但是只要不是死循环，可以多次迭代直至算出结果；
绝大多数递归，都可以使用循环实现；
即使递归代码很简洁，但是能不用则不用递归。
3、递归练习：
求 n 的阶乘：
# 循环实现 n = 6 value = 1 for i in range(1, n+1): value = (i * value) print(value) # 递归实现 def fib(n): return 1 if n == 1 else n * fib(n-1) print(fib(6))