递归:
(1)去的过程就是不停的开辟栈帧空间,在回的时候,就是在不停的释放栈帧空间,
递归函数就是不停的开辟和释放栈帧空间的一个完整的过程
(2)回的时候有两种触发的机制,要么是最后一层函数空间全部执行完毕,要么是遇到return,都会触底反弹(回马枪).
(3)写递归函数时候,必须给与跳出的条件,如果递归的层数过多,不推荐使用,容易内存溢出或者蓝屏
(4)递归调用每一层空间都是独立的个体,独立的副本,资源不共享,可以通过return来完成值的传递

官方说法,递归最大深度是1000层,具体按照机器来看

def deepfunc():
    deepfunc()
    
报错：
[Previous line repeated 996 more times]

3. 个人总结

递归就是一个函数调用自己的过程，一旦发现递归，就要考虑回的过程；递的过程只是寻找最终值或者return，不做任何结果输出，我们运算的结果主要是归的过程返回的值；就像在幽谷里面停回声。

二、求任意数n的阶乘练习

1. 普通方法

def func(n):
	total = 1
	for i in range(1,n+1):
		total *= i
		"""
		total = total * i => 1 * 1
		total = total * i => 1 * 1 * 2
		total = total * i => 1 * 1 * 2 * 3
		total = total * i => 1 * 1 * 2 * 3 * 4 
		total = total * i => 1 * 1 * 2 * 3 * 4 * 5
		"""
	return total
res = func(5) 
print(res)

2. 递归方法

def func(n):
	if n <= 1:
		return 1
	return n * func(n - 1)

res = func(5)
print(res)

# 代码解析:
# 去的过程
n = 5  return 5 * func(5 - 1) => 5*func(4)
n = 4  return 4 * func(4 - 1) => 4*func(3)
n = 3  return 3 * func(3 - 1) => 3*func(2)
n = 2  return 2 * func(2 - 1) => 2*func(1)
n = 1  return 1

# 回的过程
n = 2  return 2*func(1) => 2*1       [func(2)]
n = 3  return 3*func(2) => 3*2*1     [func(3)]
n = 4  return 4*func(3) => 4*3*2*1   [func(4)]
n = 5  return 5*func(4) => 5*4*3*2*1 [func(5)]
res = func(5) <=> 5*4*3*2*1 = 120
"""

# 通俗点
看着这个式子，n=5时，不满足<=1，跳到func(n-1)中，开始计算func(4)，依旧不满足，直到n=1,才可以直接return 1；
到达终点后开始反弹，回到2，得出return 2 * 1，回到3，得出3 * func(2)也就是3*2*1，以此类推

3. 尾递归方法

递归是每层开辟一块空间，尾递归是特殊的递归，特点是直接在原空间上面开辟，无论调用多少次函数,都只占用一份空间
好处: 只需要考虑最后一层空间的结果是多少,就不用额外考虑回的过程了;
注意：尾递归需要把值放到参数中运算

def jiecheng(n,endval=1):
	if n <= 1:
		return endval	
	return jiecheng(n-1, endval*n)
print(jiecheng(5))

# 代码解析:
# 去的过程
n = 5,endval = 1  
	return jiecheng(5-1,endval*n ) => return jiecheng(4,1*5)
n = 4,endval = 1*5
	return jiecheng(4-1,endval*n ) => return jiecheng(3,1*5*4)
n = 3,endval = 1*5*4
	return jiecheng(3-1,endval*n ) => return jiecheng(2,1*5*4*3)
n = 2,endval = 1*5*4*3
	return jiecheng(2-1,endval*n ) => return jiecheng(1,1*5*4*3*2)
n = 1,endval = 1*5*4*3*2
	if 1 <= 1  条件满足 return endval => return 1*5*4*3*2
	
# 回的过程
n = 2  return 1*5*4*3*2
n = 3  return 1*5*4*3*2
n = 4  return 1*5*4*3*2
n = 5  return 1*5*4*3*2
到此程序全部结束;
"""

为什么尾递归不需要考虑回的过程呢，因为函数目的是return endval，而endval的值已经在计算过程中出来了，即使返回上一层，程序会默认目的已达成，继续返回。
为什么要参数默认写死endval=1呢，因为阶乘就是1*2*。。。这种格式，我们需要给一个初始值，意味着这个1不是固定的，是根据实际情况来，写死也是为了用户只关注n的值即可

三、斐波那契数列练习

1. 递归写法

def feb(n):
	if n ==1 or n == 2:
		return 1
	# 当前值n = 上一个值(n-1) + 上上个值(n-2)
	return feb(n-1) + feb(n-2)

res = feb(5)
print(res)


#代码解析:
斐波那契数列的定义是：第一个数为1，第二个数为1，从第三个数开始，每个数均为前两个数之和。

n = 5 
return feb(4) + feb(3)
       feb(3) + feb(2) + feb(3)
       feb(2) + feb(1) + feb(2) + feb(3)
       feb(2) + feb(1) + feb(2) + feb(2) + feb(1)
       1+1+1+1+1=5

首先，我们将函数调用 feb(5) 传入参数5。
在函数内部，我们首先判断n的值是否等于1或2。由于5不等于1或2，所以我们将跳过这个条件语句。

接下来，我们将执行这行代码 return feb(n-1) + feb(n-2)，由于n等于5，因
此时我们需要求出斐波那契数列的第5个数。根据斐波那契数列的定义，第5个数应该是前两个数之和，即第4个数和第3个数之和。

然后，我们需要计算 feb(4) 和 feb(3) 的值。首先，我们将调用 feb(4)。
在 feb(4) 函数内部，我们也需要计算斐波那契数列的第4个数，即第3个数和第2个数之和。因此，我们需要调用 feb(3) 和 feb(2) 来计算这个值。

在 feb(3) 函数内部，我们需要计算斐波那
那契数列的第3个数，即第2个数和第1个数之和。因此，我们需要调用 feb(2) 和 feb(1) 来计算这个值。



在 feb(2) 函数内部，由于 n 的值等于2，因此我们将直接返回1。

在 feb(1) 函数内部，由于 n 的值等于1，因此我们也将直接返回1。

现在，我们已经得到了 feb(2) 和 feb(1) 的值，因此我们可以计算 feb(3) 的值。根据斐波那契数列的定义，第3个数应该是前两个数之和，即1+1=2。因此，feb(3) 的返回值为2。

接下来，我们已经得到了 feb(3) 和 feb(2) 的值，因此我们可以计算 feb(4) 的值。根据斐波那契数列的定义，第4个数应该是前两个数之和，即2+1=3。因此，feb(4) 的返回值为3。

现在，我们已经得到了 feb(4) 和 feb(3) 的值，因此我们可以计算 feb(5) 的值。根据斐波那契数列的定义，第5个数应该是前两个数之和，即3+2=5。因此，feb(5) 的返回值为5。

最后，我们在主函数中将 feb(5) 的返回值打印出来，结果为5。

因此，这段代码的执行过程可以总结如下：

调用 feb(5) 函数来计算斐波那契数列的第5个数。

feb(5) 函数内部调用 feb(4) 和 feb(3) 函数来计算斐波那契数列的第4个数和第3个数。

feb(4) 函数内部调用 feb(3) 和 feb(2) 函数来计算斐波那契数列的第3个数和第2个数。

feb(3) 函数内部调用 feb(2) 和 feb(1) 函数来计算斐波那契数列的第2个数和第1个数。

feb(2) 函数内部直接返回值1。

feb(1) 函数内部直接返回值1。

feb(3) 函数内部得到 feb(2) 和 feb(1) 的返回值后，计算斐波那契数列的第3个数为2。

feb(4) 函数内部得到 feb(3) 和 feb(2) 的返回值后，计算斐波那契数列的第4个数为3。

feb(5) 函数内部得到 feb(4) 和 feb(3) 的返回值后，计算斐波那契数列的第5个数为5。

主函数将 feb(5) 的返回值打印出来，结果为5。