递归函数

递归：函数间接或者直接调用自己
优点：简洁，理解容易
缺点：对递归深度有限制，消耗资源大

递归分两个过程
往下调用，分解的过程
往上回溯，综合的过程
递归需要注意
一定要有结束条件
是以资源换取编写速度
python对递归深度有限制，超过限制报错

# 递归函数深度限制代码x=0deffun():globalx x+=1print(x)# 函数自己调用自己fun()fun()# RecursionError: maximum recursion depth exceeded while calling a Python object

# func_a 表示计算阶乘# 利用数学公式deffunc_a(n):print(n)ifn==1:return1returnn*func_a(n-1)rst=func_a(5)print("f(5) = ",rst)

斐波那契额数列
一列数字，第一个值为1，第二个值为1，从第三个开始，每个数字的值等于前两个数字出现的值的和。

# 斐波那契额数列deffib(n):ifn==1orn==2:#公式 f(n) = f(n-1) + f(n-2) n>=3return1# f(n) = 1, n = {1,2}returnfib(n-1)+fib(n-2)rst=fib(10)print("rst = ",rst)

注解：汉诺塔规则：1每次只能移动一个盘子，2任何一次移动，三个塔的状态必须是小盒子在上，大盒子在下

# 汉诺塔a='A'b='B'c='C'defhano(a,b,c,n):ifn==1:print("{}-->{}".format(a,c))returnNoneifn==2:print("{}-->{}".format(a,c))print("{}-->{}".format(a,b))print("{}-->{}".format(b,c))returnNonehano(a,c,b,n-1)print("{}-->{}".format(a,c))hano(b,a,c,n-1)hano(a,b,c,5)

hano(a,b,c,5)
输出结果