递归的概念很简单，如果函数包含了对其自身的调用，该函数就是递归的。

递归（Recursion），在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

在使用递归时，需要注意以下几点：

递归就是在过程或函数里调用自身

必须有一个明确的递归结束条件，称为递归出口。

注意： 切勿忘记递归出口，避免函数无限调用。

递归基本步骤

每一个递归程序都遵循相同的基本步骤： 

1.初始化算法。递归程序通常需要一个开始时使用的种子值（seed value）。要完成此任务，可以向函数传递参数，或者提供一个入口函数，这个函数是非递归的，但可以为递归计算设置种子值。 

2.检查要处理的当前值是否已经与基线条件相匹配（base case）。如果匹配，则进行处理并返回值。 

3.使用更小的或更简单的子问题（或多个子问题）来重新定义答案。 

4.对子问题运行算法。 

5.将结果合并入答案的表达式。 

6.返回结果。

基线条件（base case）。基线条件是递归程序的最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件，而且必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间。

主要应用范围

递归算法一般用于解决三类问题：

（1）数据的定义是按递归定义的。（比如Fibonacci函数）

（2）问题解法按递归算法实现。（回溯）

（3）数据的结构形式是按递归定义的。（比如树的遍历，图的搜索） 　

典型的算法

大多数学过数学、计算机科学或者读过编程相关书籍的人，想必都会遇到阶乘：

n! = 1 × 2 × 3 × … × n

也可以用递归方式定义：

n! = (n-1)! × n

其中，n >= 1，并且 0! = 1。

由于简单、清晰，因此其常被用作递归的示例。

PS： 除了阶乘以外，还有很多算法可以使用递归来处理，例如：斐波那契数列、汉诺塔等。

非递归实现

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

阶乘函数的递归实现

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

递归过程

为了明确递归步骤，对 5! 进行过程分解：

factorial(5)                        # 第 1 次调用使用 5
5 * factorial(4)                    # 第 2 次调用使用 4
5 * (4 * factorial(3))              # 第 3 次调用使用 3
5 * (4 * (3 * factorial(2)))        # 第 4 次调用使用 2
5 * (4 * (3 * (2 * factorial(1))))  # 第 5 次调用使用 1 
5 * (4 * (3 * (2 * 1)))             # 从第 5 次调用返回
5 * (4 * (3 * 2))                   # 从第 4 次调用返回
5 * (4 * 6)                         # 从第 3次调用返回
5 * 24                              # 从第 2 次调用返回
120                                 # 从第 1 次调用返回

还是这个函数factorial(N)，让我们试试N = 999和N = 1000，问题来了，N = 999时能输出正确答案，但当N = 1000时，就出现下面的错误了：

RuntimeError: maximum recursion depth exceeded

于是，请记住，默认的Python有一个可用的递归深度的限制，以避免耗尽计算机中的内存。默认是1000。　

递归优缺点

优点：

递归使代码看起来更加整洁、优雅

可以用递归将复杂任务分解成更简单的子问题

使用递归比使用一些嵌套迭代更容易

缺点:

递归的逻辑很难调试、跟进

递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：mmqy2019@163.com进行举报，并提供相关证据，查实之后，将立刻删除涉嫌侵权内容。

猜你喜欢

• Python中求图片数据集均值方差的代码是什么

  这篇文章主要为大家介绍了Python计算图片数据集的均值方差，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

• Python如何生成随机数据的，随机性和安全性是怎样

  在日常工作编程中存在着各种随机事件，同样在编程中生成随机数字的时候也是一样，随机有多随机呢？在涉及信息安全的情况下，它是最重要的问题之一。每当在 Python 中生成随机数据、字符串或数字时，最好至少大致了解这些数据是如何生成的。用于在 Python 中生成随机数据的不同选项，然后在安全性、多功能性、用途和速度方面对每个选项进行比较。本篇内容不是数学或密码学相关内容，仅仅是根据需要进行尽可能多的数学运算仅此而已。

• Python中yield的作用是什么，使用写法是怎样

  yield的作用返回一个可以用来迭代（for循环）的生成器，它的应用场景通常为一个需要返回一系列值的，含有循环的函数中。

• 浏览器用selenium自动化测试的操作是什么

  浏览器常用基本操作有很多种，今天给大家介绍python3+selenium4自动化测试的操作方法，是最最基础的一篇，对python3 selenium4自动化测试相关知识感兴趣的朋友一起看看吧

• Python中读取文本文件有哪些方法，用法是怎样

  在Python中，有几种方法可以读取文本文件。在本文中，将介绍以下几种方法：open() 函数、read() 方法、readline() 方法、readlines() 方法、close() 方法和 with 关键字。需要的同学可以参考一下