课时22:函数:递归是神马

目录:

  一、递归是“神马”?

  二、写一个求阶乘的函数

  三、课时22课后习题及答案

*********************

一、递归是“神马”?

*********************

递归这个概念,是算法的范畴。那么递归算法在日常编程中有哪些例子呢?

            图片一 汉诺塔游戏

            图片二 树结构的定义

            图片三 谢尔宾斯基三角形

            图片四 女神自拍

递归,从原理上来说就是函数调用自身的一个行为。你没听错,在函数内部,你可以调用所有可见的函数,当然包括自己。

举个例子:

>>> def recursion():
    return recursion()

>>> recursion()
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    recursion()
  File "<pyshell#2>", line 2, in recursion
    return recursion()
  File "<pyshell#2>", line 2, in recursion
    return recursion()
  File "<pyshell#2>", line 2, in recursion
    return recursion()
  [Previous line repeated 990 more times]
RecursionError: maximum recursion depth exceeded

这个例子尝试了初学者玩递归最容易出现的错误。从理论上来讲,这个程序会一直执行下去,直到消耗完所有的内存资源。不过Python出于善意的保护,对递归的深度默认限制为100层,所以代码才会停下来。不过如果使用写网络爬虫的工具,可能会爬的很深,那你也可以自己设置递归的深度限制。方法如下:

>>> import sys
>>> sys.setrecursionlimit(1000000)#将递归限制设置为100万层

可用ctrl + c 让程序停止。

****************************

二、写一个求阶乘的函数

*****************************

写一个求阶乘的函数
—正整数阶乘指从1乘以2乘以3乘以4一直乘到所要求的数。
—例如所给的数是5,则阶乘式是1×2×3×4×5,得到的积是120,所以120就是4的阶乘。

非递归版本:

def factorial(n):
    result = n
    for i in range(1, n):
        result *= i

    return result

number = int(input('请输入一个正整数:'))
result = factorial(number)
print("%d 的阶乘是:%d" % (number, result))

递归版本:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

number = int(input('请输入一个正整数:'))
result = factorial(number)
print("%d 的阶乘是:%d" % (number, result))

程序实现结果:

请输入一个正整数:5
5 的阶乘是:120

我们说麻雀虽小,却五脏俱全。这个例子满足了递归的两个条件:

(1)调用了函数的本身。

(2)设置了正确的返回条件。

上面程序的详细分析如图所示:

不要忘了,递归的实现可以是函数自个儿调用自个儿,每次函数的调用都需要进行压栈,弹栈,保存和恢复寄存器的栈操作,所以在这上边是非常消耗时间和空间的。

另外,如果递归一直忘了返回,或者错误的设置了返回条件,那么执行这样的递归代码就会变成一个无底洞:只进不出!所以在写递归代码时,要记住:递归递归,归去来兮!

*******************************

三、课时22课后习题及答案

*******************************

发表回复