L22 Python 递归和迭代 扩展阅读

foxdai

递归、迭代
区别在于：递归是由自己延伸出去的，而迭代是得到新的结果并替代了自己；
“迭代”：是指重复过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。
“递归”：是指函数、过程、子程序在运行过程中直接或间接调用自身而产生的重入现象。在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。

举例：菲波那切数列：
（1）递归法：（始终调用自身函数，直到已知结果）
def fib(n):
        if n < 2:
#退出机制
                return n
        else:
#斐波那契的精髓体现;
                return fib(n-1)+fib(n-2)
#显示：
for i in range(1,x)
        print(fib(i),end=',')

（2）迭代法：(结果去替代新的变量）
def fib(x):
#初始默认值并显示
        y1 = 1
        y2 = 1
        print(y1,',',y2,end=',')
#计算需要的数值
        for i in range(1,x):
#斐波那契的精神体现，并显示；
                y3 = y2+ y1
                print(y3,end=',')
#迭代的精髓，前移替换；
                y1 = y2
#迭代的精髓，计算的新值y3替换掉前一个数y2
                y2 =y3

递归recursion和迭代iterate

（1）递归（栈）：重复多次调用程序或函数本身
理解1：递归实际上不断地深层调用函数，直到函数有返回才会逐层的返回；因此，递归涉及到运行时的堆栈开销（参数必须压入堆栈保存，直到该层函数调用返回为止），所以有可能导致堆栈溢出的错误；但是递归编程所体现的思想正是人们追求简洁、将问题交给计算机，以及将大问题分解为相同小问题从而解决大问题的动机。

理解2：递归的基本概念：程序调用自身的编程技巧称为递归，是函数自己调用自己；可以极大的减少代码量，递归的能力在于用有限的语句来定义对象的无限集合；

递归的2个要点：
（1.1）递归就是在过程或函数里面调用自身；
（1.2）在使用递归时，必须有一个明确的递归结束条件，称为递归出口

递归的2个阶段：
（阶段1）递推：把复杂的问题的求解推到比原问题简单一些的问题的求解；
（阶段2）回归：当获得最简单的情况后，逐步返回，依次得到复杂的解；
由于递归的引起一系列的函数调用，并且有可能会有一系列的重复计算，递归算法的执行效率相对较低；

#递归的劣势
1、容易产生“栈溢出”错误（stack overflow）
2、效率方面，递归可能存在冗余计算


（2）迭代：（一个程序或函数循环迭代多次）
理解1：迭代大部分时候需要人为的对问题进行剖析，将问题转变为一次次的迭代来逼近答案。迭代不像递归一样对堆栈有一定的要求，另外一旦问题剖析完毕，就可以很容易的通过循环加以实现。迭代的效率高，但却不太容易理解，当遇到数据结构的设计时，比如图‘表、二叉树、网格等问题时，使用就比较困难，而是用递归就能省掉人工思考解法的过程，只需要不断的将问题分解直到返回就可以了。
理解2：迭代，利用变量的原值推算出变量的一个新值，如果递归是自己调用自己的话，迭代就是A不停的调用B。

总结：迭代更为底层一些；递归更为高级一些，更抽象一些；所以，有“迭代为人，递归为神”的说法。
递归中一定有迭代，但是迭代中不一定有递归，大部分可以相互转换，能用迭代的不用递归，递归调用函数，浪费空间，并且递归太深容易造成堆栈的溢出。
递归是迭代的特例；

结构上的区别：
递归：选择结构，例如if else调用自己，并在合适时机退出；
迭代：循环结构，例如for, while循环

递归：本质就是被定义的项在定义完成之前，定义内部又用到了这个项；
迭代：每一次迭代都是完整的过程，并替代之前的一个版本，

形式上的区别：在启动下一个相同的过程（可以是参数不同）之前，上一个过程是否完成？


##循环、迭代、递归、遍历
循环和迭代的共同点在于，它们都是在描述一个多次操作。
不同点在于，【循环】侧重于描述每次操作和上一次操作相同之处，而【迭代】侧重于描述每次操作和上一次操作的不同之处。

##尾递归（https://blog.51cto.com/nxlhero/1231228）
一个递归过程，如果它的计算过程是迭代的，那么我们称这种递归为尾递归。尾递归不需要保存递归的推迟计算链，那么是不是就意味着不会造成栈溢出了？

递归和迭代的案例：
汉诺塔
目录索引
快速排序：20世纪10大算法
树结构
手机拍照递归
二叉树遍历的递归算法
全排列
斐波那契排列
背包问题
旅行商问题
尾递归

示例形象理解
累加：
递归：
6+add(5)
6+5+add(4)
6+5+4+add(3)
6+5+4+3+add(2)
6+5+4+3+2+add(1)
6+5+4+3+2+1+add(0)
6+5+4+3+2+1+(0)
6+5+4+3+2+(1)
6+5+4+3+(3)
6+5+4+(6)
6+5+(10)
6+(15)

def cumsum(x):
        if x:
                return x + cumsum(x-1)
        else:
                return 0

迭代：
6+5+4+3+2+1+0
6+5+4+3+2+(1)
6+5+4+3+(3)
6+5+4+(6)
6+5+(10)
6+(15)
def cumsum(x):
        result = 0
        for i in range(x+1):
                result += i
        return result

递归图解

L2201递归图解

递归一般用于解决三类问题：
　  (1)数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）
　  (2)问题解法按递归实现。（回溯）
　  (3)数据的结构形式是按递归定义的。（二叉树的遍历，图的搜索）

尾递归
　　顾名思义，尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。

尾递归的2个特点：
(1) 尾递归，比线性递归多一个参数，这个参数是上一次调用函数得到的结果；
(2) 尾递归，最后调用的是一个函数，

尾递归，可以被优化为迭代
所以，关键点在于，尾递归每次调用都在收集结果，避免了线性递归不收集结果只能依次展开消耗内存的坏处。

用“斐波那契数列”举例：计算第n个的数值
（1）递归(线性递归)
def fib(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

(2) 尾递归(计算第n个数)
def tailfib(n,y1,y2):
    if n == 0:
        return y1
    else:
        return tailfib(n-1,y2,y1+y2)
说明：(1)n,为引进的新参数；
         （2）最后调用，且为函数值

(3)迭代（循坏）
def fib(n):
    y1 =1
    y2 =1
    for i in range(n+1):
           y3 = y1+y2
           y1 = y2
           y2 = y3
    print(y3)