Python教程之递归

Python教程之递归

递归函数(Recursive Function)

  1. 有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是从前有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是从前有座山……上面的故事形成了一种无限循环,永远也讲不完。我们可以用while循环来实现,以下是代码示例:
    >>> s = "从前有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是"
    
    >>> while True:
    
    print(s)

    上面的无限循环,虽然我们用现在的知识还无法让for循环实现,但通过技巧,也是可以用for循环实现的。在Python中,还有一种方式可以实现,那就是用递归法,它的英文名是recursive。什么是递归呢?简单地说就是在函数中调用了自己。下面我们来定义一个这样的函数:

>>> def rec():              # 定义函数

print("从前有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是:")

rec()                 # 调用自己

>>> rec()
  1. 上面的函数,当打印了字符串后,又调用了自己,所以它会形成无限循环。在一般的程序设计中不要使用它,否则就会“跌入无底深渊”。怎么结束这种无限循环?请看下例代码:
  2. >> def rec(level):
    
    if level > 0 :
    
    print("从前有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是:")
    
    rec(level-1)
    
    return
    
    >>> rec(3)
    
    从前有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是:
    
    从前有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是:
    
    从前有座山,山上有座庙,庙里有个老和尚,他在讲故事,讲的是什么呢?讲的是:

    下面我们来分析一下当调用rec(3)函数时的运行过程。

  3. python递归调用分析图
  4. 我们看到,当rec(3)执行时,由于3大于0,所以它会先打印并且调用rec(2)。基于同样的道理,rec(2)也是由于2大于0,它也会先打印,然后再调用rec(1)。rec(1)也是一样,一直会调用到rec(0),由于0大于0不成立,它并不会打印,会直接运行到return返回。rec(0)运行完毕后也就意味着rec(1)运行完毕,依此类推,最后就会运行到标记为14的return语句,整个rec(3)的运行过程才结束。上面的圆形标记,从1到10是“递”的过程,从11到14是“归”的过程。通过给函数设定level参数,实现了rec(3)函数的“递”和“归”的过程。接下来分析一个经典示例,用递归法求阶乘。

    阶乘(Factorial )

  5. 计算阶乘是递归程序设计的一个经典示例。要求出某个数的阶乘就是用那个数去乘以所有比它小的自然数(大于0)。例如,factorial(5)等价于5*4*3*2*1,而factorial(3)等价于 3*2*1。阶乘的一个有趣的特性是,某个数的阶乘等于起始数乘以比它小1的数的阶乘。例如,factorial(5)与5 * factorial(4)相同。这也就是说factorial(n) = n * factorial(n-1)。这其实是一种递归的定义,所以我们可以定义递归函数来求n的阶乘。
  6. >>> def f(n):
    
    return n * f(n-1)
    
    
    >>> f(3)

    上面定义了名为f的递归函数,当调用f(3)时,调用情况大概如下所示:

    f(3) -> 3 * f(2) -> 2 * f(1) -> 1 * f(0) -> 0 * f(-1) -> -1 * f(-2)………

    当运行上面的函数,程序马上会报错,错误提示为:

    RecursionError: maximum recursion depth exceeded

    上面表示的意思是:递归错误:超过了最大的递归深度,即超过了最多调用次数。

    由于上面定义的f函数没有编写结束条件,所以理论上它会“无限”地运行下去。可是Python可不会让这种行为发生,它会对递归的调用次数进行限制,默认最多只能调用1000次。通过导入sys模块,可以用sys.getrecursionlimit命令查看最大的递归次数限制。由于1的阶乘就是1,所以n大于1递归才有意义,否则n到1了直接让它返回1即可。以下是改进的求阶乘的函数:

  7. >>> def f(n):
    
    if n >1 :
    
    return n * f(n-1)
    
    else:
    
    return 1
    
    
    
    >>> f(3)
    
    >>> 6

     

    如果n等于3,f(3)的运行过程如下图所示

    Python递归求阶乘分析图当调用f(3)时,根据条件判断语句,由于3大于1,所以它会返回 3 * f(2),那么f(2)被调用,由于2大于1,所以它会返回2*f(1)。f(1)的结果就是1,所以2*f(1)的结果是2,那么3*f(2)的结果就是6,最后f(3)就能返回6了。

  • 请给下列递归函数加上结束条件。
  • >>> def func(number):
    
    print(number)
    
    func(number-1)

    下列是有错误的求自然数和的递归函数,请修改成正确的代码。

  • >>> def zsum(n):
    
    if n > 1:
    
    return n + zsum(n)
    
    else:
    
    return n

    阅读下列代码,说出每行代码的意思,你能想像得出它会画大致什么图形吗?

  • from turtle import *
    
    t = Turtle(visible=False)
    
    def draw_square(t,length,level):
    
       if level > 0 :
        for i in range(4):
          t.fd(length)
          t.right(90)
    
    draw_square(t,length//4 ,level-1)
    
    draw_square(t,100,3)
李兴球

李兴球的博客是Python创意编程原创博客

评论已关闭。