递归有什么用呢?

可以用于解决很多算法问题，把复杂的问题分成一个个小问题，比如求斐波那契数列、汉诺塔、多级评论树、二分查找、求阶乘等。用递归求斐波那契数列、汉诺塔 对初学者来讲可能理解起来不太容易，所以我们用阶乘和二分查找来给大家演示一下。

求阶乘

任何大于1的自然数n阶乘表示方法：

n!=1×2×3×……×n

或

n!=n×(n-1)!

即举例：4! = 4x3x2x1 = 24

用递归代码来实现

def factorial(n):
 
    if n == 0: #是0的时候，就运算完了
        return 1
    return n * factorial(n-1) # 每次递归相乘，n值都较之前小1 
 
d = factorial(4)
print(d)

2分查找

我们首先引入这样一个问题：如果规定某一科目成绩分数范围：[0,100]，现在小明知道自己的成绩，他让你猜他的成绩，如果猜的高了或者低了都会告诉你，用最少的次数猜出他的成绩，你会如何设定方案?(排除运气成分和你对小明平时成绩的了解程度)

1）最笨的方法当然就是从0开始猜，一直猜到100分，考虑这样来猜的最少次数：1(运气嘎嘎好)，100(运气嘎嘎背);

2）其实在我们根本不知道对方水平的条件下，我们每一次的猜测都想尽量将不需要猜的部分去除掉，而又对小明不了解，不知道其水平到底如何，那么我们考虑将分数均分，

将分数区间一分为2，我们第一次猜的分数将会是50，当回答是低了的时候，我们将其分数区域从【0,100】确定到【51,100】;当回答高了的时候，我们将分数区域确定到【0,49】。这样一下子就减少了多余的50次猜想(从0数到49)(或者是从51到100)。

3）那么我们假设当猜完50分之后答案是低了，那么我们需要在【51,100】分的区间内继续猜小明的分数，同理，我们继续折半，第二次我们将猜75分，当回答是低了的时候，我们将其分数区域从【51,100】确定到【76,100】;当回答高了的时候，我们将分数区域确定到【51,74】。这样一下子就减少了多余的猜想(从51数到74)(或者是从76到100)。

4）就此继续下去，直到回复是正确为止，这样考虑显然是最优的

转换成代码

在一个已排序的数组data_set中，使用二分查找n，假如这个数组的范围是[low...high]，我们要的n就在这个范围里。查找的方法是拿low到high的正中间的值，我们假设是mid，来跟n相比，如果mid>n，说明我们要查找的n在前数组data_set的前半部，否则就在后半部。无论是在前半部还是后半部，将那部分再次折半查找，重复这个过程，知道查找到n值所在的地方。

代码：

#data_set = [1,3,4,6,7,8,9,10,11,13,14,16,18,19,21]
data_set = list(range(101)) 
 
def b_search(n,low,high,d):
 
    mid = int((low+high)/2) # 找到列表中间的值
    if low == high:
        print("not find")
        return
    if d[mid] > n: # 列表中间值>n, 代数要找的数据在左边
        print("go left:",low,high,d[mid])
        b_search(n,low,mid,d) # 去左边找
    elif d[mid] < n: # 代数要找的数据在左边
        print("go right:",low,high,d[mid])
        b_search(n,mid+1,high,d) # 去右边找
    else:
        print("find it ", d[mid]) 
 
b_search(188, 0,len(data_set),data_set)

那需要找多少次呢?

go right: 0 101 50
go right: 51 101 76
go right: 77 101 89
go right: 90 101 95
go right: 96 101 98
go right: 99 101 100
not find

最多将会操作7次，其实因为每一次我们都抛掉当前确定的区间的一半的区间作为不可能解部分，那么相当于求最多操作次数，就是在区间内，最多将有多少个一半可以抛去、那么就是将100一直除以2，直到不能除为止。

那么这个运算过程，其实就是相当于求了一个log2(100)≈7。

补充：

在讲特性时，我们说递归效率不高，因为每递归一次，就多了一层栈，递归次数太多还会导致栈溢出，这也是为什么python会默认限制递归次数的原因。但有一种方式是可以实现递归过程中不产生多层栈的，即尾递归，

尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

尾递归例子

def calc(n):
    print(n - 1)
    if n > -50:
        return calc(n-1)

我们之前求的阶乘是尾递归么?

def factorial(n):
 
    if n == 0: #是0的时候，就运算完了
        return 1
    return n * factorial(n-1) # 每次递归相乘，n值都较之前小1 
 
d = factorial(4)
print(d)

上面的这种递归计算最终的return操作是乘法操作。所以不是尾递归。因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值，因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。