要说递归先说迭代,迭代很好理解.
迭代:
首先说可迭代对象:可迭代对象并不是指某种具体的数据类型，它是指存储了元素的一个容器对象,如list、tuple、dict、set、str等.
那么迭代就可以理解为:通过重复执行的代码处理存可迭代对象这个元素容器的过程，并且本次迭代的处理数据要依赖上一次的结果继续往下做，上一次产生的结果为下一次产生结果的初始状态，如果中途有任何停顿，都不能算是迭代。
愚公移山,愚公挖山,愚公的儿子挖山,愚公儿子的儿子挖山……,山是一个容器,山里头每一铁锹土都是一个元素,挖山是一个重复的处理过程——所以愚公移山就是一种迭代.我们的祖先在很早很早之前就将迭代的思想应用到生活中了……
# 程序示例:
list=[1,2,3,4]
it = iter(list) # 创建迭代器对象
for x in it:
print (x, end=" ")
递归和尾递归:
编程中的递归体现为在函数中自己调自己,且函数中预备了一个函数出口.传统的递归中，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果。以这种方式，在每次递归调用返回之前，不会得到计算结果.
一般的递归
# 用经典的例子来阐述——连续整数求和
def normal_recursion(n):
if n == 1:
return 1
else:
return n + normal_recursion(n-1)
执行方式
normal_recursion(5)
5 + normal_recursion(4)
5 + 4 + normal_recursion(3)
5 + 4 + 3 + normal_recursion(2)
5 + 4 + 3 + 2 + normal_recursion(1)
5 + 4 + 3 + 3
5 + 4 + 6
5 + 10
15
可以看到, 一般递归, 每一级递归都产生了新的局部变量, 必须创建新的调用栈, 随着递归深度的增加, 创建的栈越来越多, 就可能造成爆栈.
尾递归
def tail_recursion(n, total=0):
if n == 0:
return total
else:
return tail_recursion(n-1, total+n)
执行方式:
tail_recursion(5, 0)
tail_recursion(4, 5)
tail_recursion(3, 9)
tail_recursion(2, 12)
tail_recursion(1, 14)
tail_recursion(0, 15)
15
可以看到, 尾递归每一级递归函数的调用变成"线性"的形式. 这时, 我们可以思考, 虽然尾递归调用也会创建新的栈, 但是我们可以优化使得尾递归的每一级调用共用一个栈.如此便可解决爆栈和递归深度限制的问题.
python开启尾递归优化,参考这篇文章:
https://www.jb51.net/article/247073.htm#_label2
