三层又去调用第二层的结果,所以!当上面这个程序运行时,第一次打印的是10,然后除上2,等于是5,再继续除,一直到了1,然后1/2是等于0的,此时就没有调用了递归,但是我还在调用上一层函数,就需要把这个数给返回出来,所以就变成后来的1,2,5,10了。
递归特性
?1.必须要有一个明确的结束条件, 否则就变成死循环导致栈溢出
?2.每次进入更深一层递归时,问题规模相比上次递归都应有所减少,这句话的以上就是说,每进入一次递归,就会解决一些东西,数据量就会越来越小,最终解决了所有的问题,如果进入一次递归没有解决问题,那么不管递归多少层都没有意义,直到导致栈溢出。
?3.递归效率比较低,递归层次过多会导致栈溢出,意思是:每当进入一次函数调用,栈就会加一层栈帧,每当函数返回,就减少一层栈帧,由于栈不是无限大小的,所以,递归调用的次数过多,会导致栈溢出。
那么有没有优化方式呢?肯定是有的
尾递归
我在知乎上找了一个特别有意思的例子来说明下什么是尾递归:
def story() {
从前有座山,
山上有座庙,
庙里有个老和尚,
一天老和尚对小和尚讲故事:story() // 尾递归,进入下一个函数不再需要上一个函数的环境了,得出结果以后直接返回。
}
def story() {
从前有座山,
山上有座庙,
庙里有个老和尚,
一天老和尚对小和尚讲故事:story(),小和尚听了,找了块豆腐撞死了 // 非尾递归,下一个函数结束以后此函数还有后续,所以必须保存本身的环境以供处理返回值。
}
尾递归,进入下一个函数不再需要上一个函数的环境了,得出结果以后直接返回。
def cal(n):
print(n)
return cal(n+1) # return代表函数的结束
cal(1) # 这个会一直打印,直到导致栈溢出
# 调用下一层的同时,自己就退出了