递归一个通俗的解释就是，在函数中调用函数本身；伪代码如下：
In [31]: def fun(): ....: fun()# 这个递归没有任何作用，只是为了说明什么是递归
递归（Recursion），在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
在使用递归时，需要注意以下几点：
- 递归就是在过程或函数里调用自身
- 必须有一个明确的递归结束条件，称为递归出口。
注意： 切勿忘记递归出口，避免函数无限调用。
使用递归计算的一些方法第一个阶乘：
阶乘的定义：
- 1的阶乘是1
- 大于1的树n的阶乘是n乘以(n-1)
def fun(n): #使用递归定义 if n == 1: return n else: return n * fun(n-1) fun(5) Out[72]: 120def fun1(n): # 使用非递归 result = n for i in range(1,n): result *= i return result fun1(5) Out[74]: 120
第二个幂函数的实现
In [38]: def power1(x,y): # 不使用递归 ....: result = 1 ....: for i in range(y): ....: result *= x ....: return result ....: In [39]: power1(2,5) Out[39]: 32In [43]: def power2(x,y): #递归实现 ....: if y == 0: ....: return 1 ....: else: ....: return x * power2(x, y-1) ....: In [44]: power2(2,5) Out[44]: 32
二分查找法
二分查找又叫折半查找：
＃二分查找的队列必须是有序的 有如下一个列表 [2,5,6,7,21,54,67,76,87,98,100] 列表中有序的，用二分法查找列表中数字87的位置。 列表共有11个元素，首先折半11/2的值取6，第六个元素值为54. 87>54 所以87在列表的后半部分中。 然后再重复以上过程，直到找到数值为止。
二分查找的函数代码：(代码为python2.7的版本)
#!/usr/bin/env python#*-* coding:utf -8 *-*#二分法查找数值import sysimport randomdef UnsortList(): ###如果没有指定参数，随机生成一个序列
list = []
long = random.randint(0,100) for i in range(long):
list.append(random.randint(0,10000)) return listdef BinarySearch(list, mark, low=0,uplow=None): #二分法查找
if not uplow:
uplow = len(list) -1 if low == uplow: assert mark == list[uplow] return uplow else:
mid = (low + uplow) // 2 if mark > list[mid]: return BinarySearch(list, mark,mid+1,uplow) else: return BinarySearch(list,mark,low,uplow=mid)
def SuijiMark(list): ###在列表中随机挑选一个要查找的数据
l = len(list)
mark = list[random.randint(0,l) - 1] return markdef main(): ####主函数
Ulist = [] print "1:随机产生列表，验证二分法"
print "2:用户自己输入数值生成列表，验证二分法"
answer = input("请输入对应的数字: ") if answer == 1:
Ulist = UnsortList()
mark = SuijiMark(Ulist) print "The list is %s" % Ulist print "The mark is %s" % mark print "The len of the list is %s " % len(Ulist) elif answer == 2:
lang = input("请输入列表长度: ") ##根据输入的数值，组成列表
for i in range(lang):
Ulist.append(input("请输入列表第%d个值：" % (i + 1)))
mark = SuijiMark(Ulist) print "the list is %s" % Ulist print "the mark is %s" % mark else: print "请输入合法的数字"
Ulist.sort()
index = BinarySearch(Ulist, mark) print "The index %s is %s" % (index, mark)if __name__ == "__main__":
main()
执行结果如下：
[root@mgto7 ~]# python erfen.py 1:随机产生列表，验证二分法2:用户自己输入数值生成列表，验证二分法 请输入对应的数字: 1The list is [4204, 3199, 8884, 4555, 4941, 5695, 5730, 7363, 5357, 7193, 532, 8270, 1173, 1526, 3278, 7526, 6461, 6470, 3962, 533, 5816] The mark is 7526The len of the list is 21 The index 18 is 7526[root@mgto7 ~]# python erfen.py 1:随机产生列表，验证二分法2:用户自己输入数值生成列表，验证二分法 请输入对应的数字: 2请输入列表长度: 5请输入列表第1个值：23请输入列表第2个值：54请输入列表第3个值：65请输入列表第4个值：87请输入列表第5个值：23the list is [23, 54, 65, 87, 23] the mark is 65The index 3 is 65