详细解读Python 递归函数!

zhaobig 2018-06-26

详细解读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。

相关推荐