代码复用与函数递归

代码复用与模块化设计：

代码复用：

把代码当成资源进行抽象

代码资源化：程序代码是一种用来表达计算的“资源”

代码抽象化：使用函数等方法对代码赋予更高级别的定义

代码复用：同一份代码在需要时可以被重复使用，而代码复用是需要我们将代码进行抽象才能达到的效果。

函数和对象是代码复用的两种主要形式

函数：将代码命名（在代码层面（对函数的或者对功能的一种抽象）建立了初步抽象）函数是对代码的一种抽象

对象：属性和方法（将一组变量或一组函数在基础之上进一步进行抽象）

对象的格式如下：<a>.<b>和<a>.<b>() 在函数之上对程序的再次组织进行抽象，实际上是一种面向对象的程序设计方法

从函数到对象，他们的抽象级别在不断提高。

函数和对象是实现代码复用的方法，是对代码进行抽象的不同级别。

对于代码复用，我们可以使用函数或对象通过封装将功能进一步的抽象，可以通过这种高层次的抽象，来完成一些更高层次的功能设计。

模块化设计：

在代码复用的基础上，程序员可以开展模块化设计，模块化设计基于一种逻辑的设计思维，叫做分而治之。

分而治之：使用函数或对象通过封装将程序划分为模块及模块间的表达

具体包括：主程序（模块与模块之间的关系）、子程序（模块）和子程序间关系

分而治之的思想是模块化设计的核心

分而治之：模块化设计是一种分而治之、分层抽象、体系化的设计思想

模块化设计：紧耦合：两个部分之间交流很多，无法独立存在

松耦合：两个部分之间交流很少，可以独立存在。他们之间有非常清晰简单的接口

我们通过函数来将一段代码与代码的其他部分分开，那么对于函数的输入参数和返回值就是这段函数与其他代码之间的交流通道，这样的交流通道越少越清晰，即所定义的函数模块越少，对于实现复杂的功能，对于定义的函数的复用可能性就会越高。

模块内部紧耦合，模块之间松耦合，他们之间可以通过局部变量可以进行大量的数据传输，但是在模块之间，函数与函数之间要尽可能的减少他们的传递参数和返回值，让他们之间以松耦合的形式进行组织，这样每一个函数才有可能被更多的函数所调用，他的代码才可能被更多的复用。

函数递归：

什么是递归呢？在函数定义中，调用函数自身的方式就是递归。

求解n的阶乘的时候，当n=0的时候，阶乘为1.

当求取其他值的阶乘的时候，阶乘为n(n-1)!

n!的定义也是一种递归形式，即第n的阶乘的值与n-1的阶乘值之间存在了一种递归和递进的关系。这就是一种递归的表达。

递归的定义中有两个关键的特性，即链条和基例。

链条：计算过程存在递归有序的链条关系。

比如n!=n(n-1)!,n!与（n-1)！就构成了递归链条

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

比如当n=0时，我们定义它的值为1，这就是一种基例，它与其它的值之间并不存在递归关系，它已经是递归的最末端。

没有链条的程序不是递归

没有基例的程序也构不成递归。

类似数学归纳法：证明一个定理成立的时候，一般我们采用数学归纳法可以这样证明

首先我们证明当n取第一个值n0时命题成立，假设当nk时命题成立，证明当n=nk+1时命题也成立，如果这两个步骤都是对的，我们就能证明某一个命题成立

递归是数学归纳法思维的编程体现。

函数递归的调用过程：

递归的实现：

求解n的阶乘的时候，当n=0的时候，阶乘为1.

当求取其他值的阶乘的时候，阶乘为n(n-1)!

递归函数在定义的时候，要满足两个基本条件：一个是递归公式，另一个是边界条件。其中，递归公式是求解原问题或相似的子问题的结构；边界条件是最小化的子问题，也是递归终止的条件。

递归函数的执行可以分为以下两个阶段
（1）递推：递归本次的执行都基于上一次的运算结果

（2）回溯：遇到终止条件时，则沿着递推往回一级一级地把值返回来。

递归函数的一般定义格式如下所示：

def 函数名（[参数列表]):

if 边界条件：

return 结果

else:

return 递归公式

我们通过递归进行该代码的编写：

代码如下所示：

def fact(n):
    if n==0:
          return 1
    else:
          return n*fact(n-1)
n=eval(input("请输入一个整数:"))
result=fact(n)
print("n!={}".format(result))

运行界面如下：

我们计算3的阶乘，当计算机进行函数的调用的时候，先判断此时n的值与0不相同，即进行调用fact(2),此时计算机分配了一段内存，分配计算资源计算他的值，我们在进行判断，此时n的值为2，与0不同，继续调用fact(1),此时函数的n与1不同，继续调用fact(0),此时n的值与0相同，返回1，然后进行回溯，将结果一级一级往回返回。即fact(1)=n*fact(0)=1*1=1,fact(2)=n*fact(1)=2*1=2,

fact(3)=n*fact(2)=3*2=6,即结果为6。将结果进行输出。

当我们使用递归函数时，我们要包含一下结构：

函数+分支语句

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

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

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

实例一：字符串反转：

将字符串s反转后输出：

在字符串里面我们已经学过，s[::-1],实现字符串反转，从最后面进行逐一的取出。

s[M:N],M缺失，表示从开头到N前面的那一个数为止。

N缺失，表示从M开始到结尾。

具体详细内容可以看此篇字符串详解的博客。http://javascript:;

函数递归需要：

函数+分支结构

递归链条

递归基例

代码示例如下：

def rvs(s):
    if s=="":
        return s
    else:
        return rvs(s[1:])+s[0]
s=input("请输入字符串：")
print(rvs(s))

运行界面如下：

通过代码我们可知运行过程如下所示：

我们调用函数rvs（s），首先判断是否为空，不为空，我们调用rvs(gfypl),再次进行判断，仍不为空，继续调用rvs(fypl),再次判断，不为空，继续调用rvs(ypl),再次进行判断，仍不为空，继续调用rvs(pl),再次判断，不为空，继续调用rvs(l),再次进行判断，仍不为空，继续调用rvs(),再次判断,为空，我们再将结果依次返回，将rvs(）返回，将rvs(l)返回，将rvs(lp)返回，将rvs(lpy)返回，将rvs(lpyf)返回，将rvs(lpyfg)返回后,再将原字符串的第一个字符加到最后及实现了字符串的反转。

实例二：斐波那契数列：

一个经典数列：

F(n)=1,n=1

F(n)=1,n=2

F(n)=F(n-1)+F(n-2),n=其他

代码示例如下：

def f(n):
    if n==1 or n==2:
        return 1
    else:
       return f(n-1)+f(n-2)
n=eval(input("请输入整数："))
print(f(n))

运行界面如下：

我们通过调用函数，先进行条件判断，n=5,不符合n==1或n==2,我们进行调用f(4)+f(3),我们分别分配两个新的内存去调用f(4)和f(3),

调用f(4)时，我们分配一个新的内存进行计算，进行判断条件，不符合，我们调用f(3)+f(2),我们再分配两个新的内存，进行分别调用f(3)和f(2),调用f(3),判断条件不符合，我们调用f(2)+f(1)条件不符合，我们再进行调用f(2）和f(1),此时条件符合，依次往上返回结果，f(2)+f(1)=2,f(3)+f(2)=3,所以f(4)=3.通过相同的思路，我们求解f(3),

调用f(3)时，我们分配一个新的内存进行计算，进行判断条件，不符合，我们调用f(2)+f(1),此时条件符合，依次往上返回结果，f(2)+f(1)=2,即f(3)=2,两者相加即为5.

实例三：汉诺塔问题：

有三根柱子，其中一个柱子上摆放有从上到下将圆盘从小到大摆放，其中一根柱子为过度柱子，另一个柱子为目标柱子，将柱子上的圆盘放到目标柱子上，而且大圆盘不能放到小圆盘上，在移动过程中，一次只能移动一个柱子。如何移动我们通过递归过程进行解决：

count=0
def hanoi(n,src,dst,mid):  #n个圆盘，src为放置圆盘的圆柱，dst为目标圆盘，mid为过渡圆盘。
    global count
    if n==1:
       print("{}:{}->{}".format(1,src,dst))
       count+=1
    else:
       hanoi(n-1,src,mid,dst)    #将放置圆盘的柱子通过过渡圆盘放到目标圆盘
       print("{}:{}->{}".format(n,src,dst))
       count+=1
       hanoi(n-1,mid,dst,src)     #将过渡圆盘通过目标圆盘放到初始圆盘的柱子
hanoi(3,'A','C','B')   #A为初始圆盘，c为目标圆盘，B为过渡圆盘。
print(count)

运行界面如图：