欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-25 16:11:00
目录: 一、递归是“神马”? 二、写一个求阶乘的函数 三、课时22课后习题及答案 ********************* 一、递归是“神马”? ********************* 递归这个概念,是算法的范畴。那么递归算法在日常编程中有哪些例子呢? 图片一 汉诺塔游戏 图片二 树结构的定义 ......

目录:

  一、递归是“神马”?

  二、写一个求阶乘的函数

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

 

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

一、递归是“神马”?

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

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

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

            图片一 汉诺塔游戏

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

            图片二 树结构的定义

课时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:函数:递归是神马

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

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

 

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

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

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

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

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

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

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