Hello，大家好！要说声抱歉了，今天说好的K均值聚类推到明天了。

今天是递归算法，请查阅！谢谢。

递归算法是一种很有用的编程思想，特别是在函数编程中。有句话，我直接从文献中搬过来，太经典了。

函数不但可以调用自身（直接递归），还可以调用其他函数，其他函数也可以再调用该函数（间接递归）。

这句话需要深刻理解并不容易，我们先看直接调用。

一、阶乘

#阶乘
import math
import time
 
def my_factorial(n):
      s=1
      for x in range(1,n+1):
            s*=x
      return s
 
#下面用递归实现
def fact(n):
      if (n==0|n==1):
            return 1    
      else:
            return n*fact(n-1)
 
#直接调用已有函数
start=time.clock()
p=math.factorial(33)
end=time.clock()
print('调用math.factorial耗时：',end-start,'\n结果为：',p,'\n')
 
start=time.clock()
k=my_factorial(33)
end=time.clock()
print('for循环定义函数耗时：',end-start,'\n结果为：',k,'\n')
 
start=time.clock()
q=fact(33)
end=time.clock()
print('递归函数耗时：',end-start,'\n结果为：',q,'\n')

运行结果如下：

调用math.factorial耗时： 3.20782915615167e-06 
结果为： 8683317618811886495518194401280000000 
 
for循环定义函数耗时： 7.37800705916114e-06 
结果为： 8683317618811886495518194401280000000 
 
递归函数耗时： 1.2510533708987026e-05 
结果为： 8683317618811886495518194401280000000

递归方法每一次都要调用函数，而且需要判断，而for循环调用一次，直接累积即可。

二、二项式系数练习

#用递归方法实现
import time
def binomial(r,n):
      if r==n:
            return 1
      elif r==1:
            return n
      else:
            return binomial(r,n-1)+binomial(r-1,n-1)
 
start=time.clock()
num=binomial(4,12)
end=time.clock()
print('自己编写的递归函数耗时',end-start,'\n结果为',num,'\n')
 
def crn(r,n):  
      if r==0: return 1  
      if n==0: return 0  
      return crn(r,n-1)+crn(r-1,n-1)
 
start=time.clock()
b=crn(4,12)
end=time.clock()
print('网上的递归函数耗时',end-start,'\n结果为',b,'\n')

运行结果如下：

自己编写的递归函数耗时 5.5495444401423894e-05 

结果为 495 

网上的递归函数耗时 0.0001988854076813984 

结果为 495 

还是我自己编写的函数厉害。很可能是我的计算步骤要少，

当r=n，肯定是1，r=1，结果肯定是n

三、请自己完成Fibonacci序列的编写。

四、折半查找法

#折半查找—递归方法实现
import numpy as np
import pandas as pd
np.random.seed(123)
num_list=np.random.randn(12)
num_list.sort()
num=num_list.round(1)
print(num)
a=1.3
#最笨方法
def num_in(a,num):
      index=range(len(num))
      left=min(index)
      right=max(index)
      while left <=right:
                  mid=(left+right)//2
                  if a<num[mid]:
                        right=mid-1
                  elif a>num[mid]:
                        left=mid+1
                  elif a==num[mid]:
                        return mid

index=num_in(a,num)
print('a是否在有序列表num里面\n返回数字则是索引,不在则为None\n',index)       

#采用递归改写上面方法
def num_in2(a,num,left,right):
      if (left<=right):
            mid=(left+right)//2
            if compare(a,num[mid])==1:
                  return num_in2(a,num,mid+1,right)
            elif compare(a,num[mid])==0:
                  return mid
            elif compare(a,num[mid])==-1:
                  return num_in2(a,num,left,mid-1)

def compare(b,c):
      if b<c:
            return -1
      elif b==c:
            return 0
      else :
            return 1

ii=range(len(num))
left=min(ii)
right=max(ii)
index2=num_in2(a,num,left,right)
print(index2)

两种方法结果是一样的，证明我的program没有问题。

欢迎持续关注，明天K均值聚类理论。

 参考文献为：清华大学朱仲涛译《数据结构基础（C语言版）》