Python代码实现算法笔记 #4 递归 基础

某些计算机编程语言允许模块或函数调用自身。 这种技术称为递归。 在递归中，函数 α 直接调用自身或调用函数 β，而函数 β 又调用原始函数 α。 函数 α 称为递归函数。

示例 - 调用自身的函数：

示例 - 一个函数调用另一个函数，而另一个函数又调用它:

特性

递归函数可以像循环一样无限循环。为了避免递归函数的无限运行，递归函数必须具有两个属性：

基本标准：必须至少有一个基本标准或条件，这样，当满足此条件时，函数将停止递归调用自身。对应前面示例中的判断是否小于 1。

渐进式方法：递归调用应该以这样一种方式进行，即每次进行递归调用时它都更接近基本条件。

底层实现

许多编程语言通过堆栈实现递归。 通常，每当函数（调用者）将另一个函数（被调用者）或其自身调用为被调用者时，调用者函数就将执行控制转移给被调用者。 该传输过程还可能涉及一些要从调用者传递给被调用者的数据。

这意味着，调用者函数必须暂时暂停其执行，并在执行控制从被调用者函数返回时稍后恢复。 在这里，调用者函数需要从执行点开始，它将自己置于保持状态。 它还需要与其正在处理的完全相同的数据值。 为此，为调用者函数创建激活记录（或堆栈帧）。

此激活记录保存有关局部变量，形式参数，返回地址和传递给调用者函数的所有信息的信息。

分析递归

有人可能会争论为什么要使用递归，因为迭代可以完成相同的任务。个原因是，递归使程序更具可读性，并且由于新的增强型CPU系统，递归比迭代更有效。

时间复杂度

在迭代的情况下，我们采用迭代次数来计算时间复杂度。 同样，在递归的情况下，假设一切都是常量，我们试图找出递归调用的次数。 对函数的调用是Ο（1），因此递归调用的（n）次数产生递归函数Ο（n）。

空间复杂度

空间复杂度计算为模块执行所需的额外空间量。 在迭代的情况下，编译器几乎不需要任何额外的空间。 编译器不断更新迭代中使用的变量值。 但是在递归的情况下，每次进行递归调用时系统都需要存储激活记录。 因此，认为递归函数的空间复杂度可能高于具有迭代的函数的空间复杂度。