《Python入门08》你知道Python递归函数怎么写吗~~

点击上方的“小小白AI”,选择“关注”

重磅知识,第一时间送达

前言

直入主题~~~

1、什么是递归函数

前面深入介绍了如何创建和调用函数。你知道,函数可调用其他函数,但可能让你感到惊讶的是,函数还可调用自己。如果你以前没有遇到这种情况,可能想知道递归是什么意思。简单地说,递归意味着引用(这里是调用)自身。

2、python递归函数

下面是一个递归式函数定义:

def recursion():

return recursion()

这个定义显然什么都没有做,与刚才的“递归”定义一样傻。如果你运行它,结果将如何呢?你将发现运行一段时间后,这个程序崩溃了(引发异常)。从理论上说,这个程序将不断运行下去,但每次调用函数时,都将消耗一些内存。因此函数调用次数达到一定的程度(且之前的函数调用未返回)后,将耗尽所有的内存空间,导致程序终止并显示错误消息“超过大递归深度”

你想要的是能对你有所帮助的递归函 数,这样的递归函数通常包含下面两部分。

 基线条件(针对小的问题):满足这种条件时函数将直接返回一个值。

 递归条件:包含一个或多个调用,这些调用旨在解决问题的一部分。

这里的关键是,通过将问题分解为较小的部分,可避免递归没完没了,因为问题终将被分解成基线条件可以解决的小问题。

3、python递归函数

那么如何让函数调用自身呢?这没有看起来那么难懂。前面说过,每次调用函数时,都将为此创建一个新的命名空间。这意味着函数调用自身时,是两个不同的函数[更准确地说,是不同版本(即命名空间不同)的同一个函数]在交流。

经典案例1,计算数字n的阶乘。n的阶乘为n × (n-1)× (n-2) ×… × 1,在数学领域的用途非常广泛。

可使用循环。这种实现可行,而且直截了当。

deffactorial(n):

result = n

for i in range(1, n):

result *= i

return result

下面来考虑如何使用函数来实现这个定义。理解这个定义后,实现起来其实非常简单。 def factorial(n):

if n == 1:

return 1

else:

return n * factorial(n -1)

这是前述定义的直接实现,只是别忘了函数调用factorial(n)和factorial(n–1)是不同的 实体。

经典案例2、计算一个数幂,就像内置函数pow和运算符**所做的那样。要定义一个数字的整数次幂,有多种方式,但先来看一个简单的定义:power(x, n)(x的n次幂)是将数字x自乘n - 1次的结果,即将n个x相乘的结果。换而言之,power(2, 3)是2自乘两次的结果,即2 × 2 × 2 = 8。

这实现起来很容易。

def power(x, n):

result = 1

for i in range(n):

result *= x

return result 这是一个非常简单的小型函数,但也可将定义修改成递归式的。

对于任何数字x,power(x, 0)都为1。n>0时,power(x, n)为power(x,n-1)与x的乘积。这种定义提供的结果与更简单的迭代定义完全相同。理解定义是难的,而实现起来很容易。

def power(x, n):

if n == 0:

return1

else:

return x* power(x, n - 1)

4、为什么要使用递归函数

大多数情况下,使用循环的效率可能更高。然而,在很多情况下,使用递归的可读性更高,且有时要高得多,在你理解了函数的递归式定义时尤其如此。另外,虽然你完全能够避免编写递归函数,但作为程序员,你必须能够读懂其他人编写的递归算法和函数。always remember you should coding~~~

参考文献:

[1]Beginning Python From Novice to Professional (Third Edition),

Magnus Lie Hetland.

希望上述内容能够帮助到正在学习的你~

原文发布于微信公众号 - AINLPer(gh_895a8687a10f)

原文发表时间:2018-09-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券