详细解读Python 递归函数！

递归函数

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。

递归函数特性：

1. 必须有一个明确的结束条件；
2. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
3. 相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
4. 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

先举个简单的例子：计算1到100之间相加之和；通过循环和递归两种方式实现

#!/usr/bin/env python3
# 1-100 sum
import sys
def sum_cycle(n):
 '''
 1 to n,The sum function
 '''
 sum = 0
 for i in range(1,n + 1):
 sum += i
 return sum
def sum_recu(n):
 '''
 1 to n,The sum function
 '''
 if n > 0:
 return n + sum_recu(n - 1)　　　　#调用函数自身
 else:
 return 0
print("循环求和：",sum_cycle(100))
print("递归求和：",sum_recu(100))
执行结果：
[root@localhost tmp]# ./sum.py
循环求和： 5050
递归求和： 5050

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

***使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

把上面的递归求和函数的参数改成10000就导致栈溢出！

[root@localhost tmp]# ./sum.py
循环求和： 5050
Traceback (most recent call last):
 File "./sum.py", line 23, in <module>
 print("递归求和：",sum_recu(1000))
 File "./sum.py", line 19, in sum_recu
 return n + sum_recu(n - 1)
 File "./sum.py", line 19, in sum_recu
 return n + sum_recu(n - 1)
 File "./sum.py", line 19, in sum_recu
 return n + sum_recu(n - 1)
 [Previous line repeated 994 more times]
 File "./sum.py", line 18, in sum_recu
 if n > 0:
RecursionError: maximum recursion depth exceeded in comparison

***解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

尾递归优化：http://www.open-open.com/lib/view/open1480494663229.html

二分法查找大家应该听说过；就是一种快速查找的方法，时间复杂度低，逻辑简单易懂，总的来说就是不断的找出中间值，用中间值对比你需要找的实际值；若中间值大，则继续找左边；若中间值小，则继续找右边；可以看出二分法就是不断重复此上过程，所以就可以通过递归方式来实现二分法查找了！

今天在 codewar 做题目玩，做到一题时，想试试用递归写，却发现在函数体内一切正常，可是打印返回值时，打印出来的结果却是 None 。不明白是在哪里除了问题了，于是在网上翻了一圈，自己又仔细思考了下整个逻辑。似乎弄清楚了。这里我来解释下我的理解。

首先，我来写一个简化的递归函数，来做用于解释的案例。

def ex(x):
 if x > 1:
 x -= 1
 ex(x)
 else:
 return x
t = ex(5)
print(t)

上面的程序逻辑超简单：判断输入的书是否大于 1 ，如果大于 1 则把它减 1 ，然后再判断。如此不断递归下去。当 x 不大于 1 的时候，返回 x 的大小。

很容易认为返回的 x 打印出来的结果是 1 是不？但是不是的。你可以把上面的代码运行下，打印出来的结果是：

None

为什么是这样的呢？我的理解是：

当我们在 t = ex(5) 的时候，调用了一次函数。如果函数直接返回 t = 1，那是木有问题的。问题是，程序在这里返回数据。反而又去调用了一次函数本身。这次调用的的是 ex(4) 然后一直调用的 ex(1) 这时候程序终于运行到了 return 这里。那这次 return 给了谁呢？答案是谁都没有给。因为我们没有设置 t = ex(1)， 所以函数的 return 回的数据就这么丢失了。

而我们调用的 t = ex(5) 呢，因为它的 if > 1 是成立的，所以直接跳过了了 else: return x ，等于这一次调用，是没有用到 return 的。而在 Python 中规定，如果一个函数体没有 return 的时候，那它的 return 就是 None 。这也就是为什么，我们运行上面的程序的时候，得到的结果是 None 。

为了证明这点，我们可以去写一个程序，去尝试获得迭代到 ex(1) 这次调用时 ex(1) 所返回的值。程序如下：

t = {}
def ex(x):
 global t
 if x > 1:
 x -= 1
 t[x] = ex(x)
 else:
 return x
ex(10)
print(t)

在程序中，我们用字典，把 ex(x) 每次调用所返回的数据记录了下来。结果如下：

{1: 1, 2: None, 3: None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None}

可见：

1. 在迭代中，后调用的函数先返回。
2. 除了最后一次调用的函数有了正确的返回外，之前的函数都没有 return ，所以返回的都是 None。

那如何正确地返回迭代出来的数据呢？答案是：一层一层第把最后一次调用返回出来。代码如下：

def ex(x):
 if x > 1:
 x -= 1
 return ex(x)
 else:
 return x
t = ex(5)
print(t)

结果为：

1

为什么这次能正确呢？因为第一次调用 ex(x) 的时候，它返回的是ex(x-1)，下一次调用返回了 ex(x-2) 一路携手交传，最终把 ex(1) return 给了 t ，这个时候就等于 t = ex(1) 了，自然就得到了正确的结果了。

嗯，本文就到这里要结束了。最后说一下， Python 的确不喜欢迭代。所以它严格限制了迭代的次数。我电脑上，只要迭代的次数超过 999 ，就会报错，如下：

t = ex(998)

1

t = ex(999)

Traceback (most recent call last):
File "E:\Work\Coder\Test\test4.py", line 14, in <module>
t = ex(999)
RecursionError: maximum recursion depth exceeded in comparison

***解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

尾递归优化：http://www.open-open.com/lib/view/open1480494663229.html

二分法查找大家应该听说过；就是一种快速查找的方法，时间复杂度低，逻辑简单易懂，总的来说就是不断的找出中间值，用中间值对比你需要找的实际值；若中间值大，则继续找左边；若中间值小，则继续找右边；可以看出二分法就是不断重复此上过程，所以就可以通过递归方式来实现二分法查找了！

#!/usr/bin/env python3
#The binary search function
def Binary_Search(data_source,find_n):
 if len(data_source) >= 1: #判断列表长度是否大于1，小于1就是一个值
 mid = int(len(data_source)/2) #获取列表中间索引；奇数长度列表长度除以2会得到小数，通过int将转换整型
 if find_n > data_source[-1]: #判断查找值是否超出最大值
 print('{}查找值不存在！'.format(find_n))
 exit()
 elif find_n < data_source[0]: #判断查找值是否超出最小值
 print('{}查找值不存在！'.format(find_n))
 exit()
 if data_source[mid] > find_n: #判断列表中间值是否大于查找值
 #print('查找值在 {} 左边'.format(data_source[mid]))
 Binary_Search(data_source[:mid],find_n) #调用自己，并将中间值左边所有元素做参数
 elif data_source[mid] < find_n: #判断列表中间值是否小于查找值
 #print('查找值在 {} 右边'.format(data_source[mid])) #调用自己，并将中间值右边所有元素做参数
 Binary_Search(data_source[mid:],find_n)
 else:
 print('找到查找值',data_source[mid]) #找到查找值
 else:
 print('{}查找值不存在！'.format(find_n)) #特殊情况，返回查找不到
Data = [22,12,41,99,101,323,1009,232,887,97]
Data.sort() #列表从小到大排序
Binary_Search(Data,323) #查找323
执行结果：
[root@localhost tmp]# ./binary_search.py 
找到查找值 323

好了，今天的知识就分享到这里，欢迎关注爱编程的南风，私信关键词：学习资料，获取更多学习资源，如果文章对你有有帮助，请收藏关注，在今后与你分享更多学习python的文章。同时欢迎在下面评论区留言如何学习python。