1、迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值
2、描述迭代的一种方法是使用显式循环，如while和for循环。另一种完全不同的迭代实现方式是递归
3、递归是一种技术，这种技术是指通过函数在执行过程中一次或者多次调用其本身，或者通过一种数据结构在其表示中依赖于相同类型的结构更小的实例。
4、递归算法效率可能没有循环高，但是可读性和代码简洁性更强！
5、函数执行导致嵌套函数的调用时，参数、局部变量和执行位置信息压栈，调用结束后恢复。递归调用也是这样的过程。当函数的依次调用需要进行递归调用时，该调用被挂起，直到递归调用完成。
6、在python中，当一个函数被调用时，为此创建一个活动记录或框架的结构来存储信息。活动记录里面存储函数调用的参数和局部变量的命名空间。函数调用自身时，也是两个不同的函数(不同命名空间)在交流。
7、如果一个函数的执行导致嵌套函数的调用（其他函数或者函数调用自身），前者的调用将被挂起，其活动记录将存储源代码中的位置（源代码中调用函数代码的下一条指令的存储位置），这个位置是调用函数返回后将继续执行的控制流。return之后根据活动记录（栈）中的参数、局部变量和源代码下一条指令的位置，执行对应的指令操作。
8、递归包含两个部分：
1、基线条件：满足基线条件则直接返回一个值。针对于最小问题！
2、递归条件：包含一个或者多个调用，一次或者多次调用函数的本身或者使用一个或者多个相同类型的结构更小的实例表示。解决问题的一部分！
1、阶乘函数
def factorial(n):
if n==0:
return 1
else:
return n*factorial(n-1)
2、二叉树的中间遍历算法，每个实例进行两次递归调用。
def inOrder(self, node):
"""中序遍历"""
if node is None:
return
self.inOrder(node.lchild)
print(node.elem, end=‘ ‘)
self.inOrder(node.rchild)
3、二分查找：在一个含有n个元素的有序序列中有效的定位目标值
def binary_search(data, target, low=0, high=len(data)-1):
if low > high:
return False
else:
mid = (low + high) // 2
if target == data[mid]:
return True
elif target < data[mid]:
return binary_search(data, target, low, mid - 1)
else:
return binary_search(data, target, mid + 1, high)
4、计算机的文件系统中的递归结构
4.1、操作系统用递归的方式定义文件系统的目录（文件夹）。一个文件系统包括一个顶级目录，这个目录的内容包括文件和其他目录，其他目录又可以包括文件和其他目录，依次类推。虽然必定有一些基本的目录只包含文件而没有下一级子目录，但是操作系统允许在系统内存空间允许条件下，嵌套任意深度的目录。
4.2、目录的复制或删除都可以使用递归算法实现（Size函数返回一个目录的即磁盘空间）
def DiskUsage(path):
total=Size(path)
if path represents adirectory then
for each child entry stored within adirectory do
total=total+DiskUsage(child)
return total
归纳法，证明递归过程正确性和有效性
对于递归算法，分写递归算法，解释基于函数的特殊激活并且被执行的每个操作，该函数在被执行期间管理控制流。另一种表达：对于每次函数调用，只解释被调用的主体内执行的操作的数目，然后，通过在每个单独调用过程中执行的操作数的总和，及所有调用次数，可以解释被作为递归算法的一部分而执行的操作数的总和。
阶乘函数 factorial(n)的操作总数是O（n），因为有 n+1 次调用，所以每次调用占的操作次数是O（1）
二分查找时间复杂度O（log n）
文件系统：for循环遍历目录下的所有条目，最坏的情况下（较弱的约束），一个条目可能包含了 n-1 个其他条目。有 O（n）个递归调用，并且每个调用运行的时间为O（n），从而导致总的运行时间为O（n2）；在较强的约束下，利用分期偿还的技术的思想，通过考虑累计效应获得一系列操作更严格的约束，在所有的递归调用中的for循环迭代的总数，断言刚好有 n-1 个该循环的这种迭代，基于该循环的每次迭代进行一次对函数的递归调用并且已经得出结论，即对函数共进行了 n 次调用（包括最开始的调用），得出结论：有O（n）次递归调用，每次递归调用在循环外部使用O（1）的时间，并且循环操作的总数是O（n）。在这些限制条件之下，操作的总数是：O（n）！
原文：https://www.cnblogs.com/yinminbo/p/11361525.html