递归
程序调用自身的编程技巧称为递归。每个递归函数有基线条件和递归条件两部分，递归条件是指函数调用自己，基线条件指的是函数不再调用自己，从而避免形成无限循环。
事例：
递归函数factorial，factorial（5）写作 5！，其定义如下5！=5*4*3*2*1。同理factorial（3）=3*2*1。
def fact(x)
if X==1: ---基线条件
return 1
else:
return x* fact(x-1) ---递归条件
这里需介绍一种叫做栈的数据结构。它是一种后进先出的数据结构，限定仅在表头进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
计算机内部使用被称为调用栈的栈存储有关正在运行的子程序的消息，调用栈最经常被用于存放子程序的返回地址。在调用任何子程序时，主程序都必须暂存子程序运行完毕后应该返回到的地址。因此，如果被调用的子程序还要调用其他的子程序，其自身的返回地址就必须存入调用栈，在其自身运行完毕后再行取回。在递归程序中，每一层次递归都必须在调用栈上增加一条地址，因此如果程序出现无限递归（或仅仅是过多的递归层次），调用栈就会产生栈溢出。
在上面的递归函数中，调用fact(3)时栈是如何变化的？
《算法图解》3.3栈执行过程：
fact(3)
fact(2) * 3
fact(1) * 2 * 3
1 * 2 * 3
2 * 3
6
在每个fact调用都有自己的X变量，在一个函数调用中不能访问另一个X变量。栈在递归中扮演着重要角色。
用循环实现
x=int(input("输入一个数字："））
fact = 1
while x>1:
fact = fact*x
x=x-1
else:
return fact
使用栈虽然很方便，但存储详尽的信息可能闸弄大量的内存。这种情况下可以改为使用循环，也可以使用尾递归。
尾递归
当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
上面递归函数用尾递归，写成如下
a = 1
def fact(x, a):
if X ==1:
return a
return fact(x -1, x *a)
执行过程：
fact(3,1)
fact(2,3)
fact(1,6)
6
递归需要fact(1)出结果后返回给fact(2)计算出结果，再返回给fact(3)。
感受：细细琢磨一些递归函数，会有让人惊叹的秒思，至少是让我惊叹的秒思。文中介绍的一些其他算法也是。前面几章比较简单所以很好理解，目前看到第七章狄克斯特拉算法已经比较吃力，需要反复的看。目标还是看完所有算法，并理解其中的精髓。写这篇笔记的时候才发现里面有些地方理解的并不是和透彻，需要反复研究才能明白。
任务完成回顾：上上周的奖励开心麻花的《窗前不止明月光》已经买了1月份的票，只等时间到了。上周定下目标是提前一天完成作业的，虽然现在写完了，但确实已经到了21号，并没有提前一天完成，这个冬天就没有新靴子了，难过。最近真的很像买个天猫精灵，看了很久，就作为下周的奖励吧。如果明天能写完，那就能再给天猫精灵买一个猫耳朵外套。为什么要明天完成？因为猫耳朵外套做特价截至到后天的15点。任务目标还是1000字以上的算法图解的读书笔记。
网友评论