函数递归思维

编程语言中，函数直接或间接调用函数本身，则该函数称为递归函数。它的定义是这样写的：一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的。

简单来说，他有两个关键特征：

链条：计算过程存在递归链条

基例：存在一个或多个不需要再次递归的基例

要实现递归函数，要熟练的明确这两个关键的特征。

递归的实现：

1、递归本身是一个函数，需要函数定义方式描述

2、函数内部，采用分支语句对输入参数进行判断

3、基例和链条，分别编写对应代码

以字符串反转为例

比如我要输入一串字符“1，2，3，4，5，6，7，8，9”.我要实现的效果是输出：“9，8，7，6，5，4，3，2，1”.因此我要确定递归的两个关键特征，链条和基例。

那这个例子的链条是什么呢？ 就是将字符串的首字符移到其余字符串的最后，这样就构成了一个反转，然后再将其余字符串的首字符放到其余字符串的其余字符的后面，又构成了一次反转，知道，最后一个其余字符为一个字符，那么它将和一个空字符进行反转，这也就是最后一步，也是递归所说的基例。

1
2
3
4
5

def rvs(s):
    if s == "":
        return s
    else :
        returnrvs (s[1:])+s[0    

以汉诺塔为例

1、对于给定数量的圆盘，从最左侧搬运到最右侧需要多少个步骤

2、要知道如何搬运的问题，把汉诺塔的三根柱子分别抽象化为ABC，再抽象化，假如有n个圆盘，要完成最后一个步骤是不是需要把n-1个圆盘搬到B柱子，然后第n个圆盘直接搬到C（这里就可以看作和n=1的情况相同，执行n=1的步骤），n-1个圆盘从B搬到C。最终完成整个过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

count = 0
def han(a,b,c,n):
    global count
    if n==1:
        print("{}:{}->{}".format(count+1,a,c))#最后一步该做的事就是把A->C
        count += 1
    else:
        han(a,c,b,n-1)   #最后一步的前一步就是，先把A->B
        print("{}:{}->{}".format(count+1,a,c))
        count+=1
        han(b,a,c,n-1)    #然后再把B->C
def main():
    han("A","B","C",6)
    print(count)
main()

汉诺塔的编程体现了计算机编程的计算思维！

参考资料:Python语言程序设计基础(第2版)》嵩天、礼欣、黄天羽著，高等教育出版社，2017.2（讲授Python 3版本）

视频课程

Python3菜鸟教程

Python官方手册