type
status
date
slug
summary
tags
category
icon
password
递归是一种算法策略， 通过函数调用自身来解决问题，主要包括两个阶段：
- 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
- 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。
从实现的角度来看， 递归代码主要包含三个要素：
- 终止条件：用于决定什么时候由“递”转“归”。
- 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
- 返回结果：对应“归”，将当前递归层级的结果返回至上一层。
递归调用的深度不宜过深，Python对递归调用的深度做了限制，以保护解释器
- 超过递归深度限制，抛出RecursionError: maximum recursion depth exceeded超出最大深度
- sys.getrecursionlimit()
观察以下代码，我们只需调用函数 recur(n) ，就可以完成 1 + 2 + ⋯ + 𝑛 的计算：
下图展示函数的求和过程：
1. 普通递归实现
当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。计算结果是在“归”过程中执行的，每层返回后还要都再执行一遍。
1.1 斐波那契数列
斐波那契数列Fibonacci number： 1,1,2,3,5,8,13,21,34,55,89,144,…
推导式为：
根据推导式，可以看出
- 时间复杂度：
- 空间复杂度：
- 递归调用的空间复杂度 = 递归深度*每次调用所需的辅助空间
递归优化
1、记忆化搜索
把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，在解决小问题的时候，记忆每一个小问题的答案，使得每个小问题只解决一次，从而避免出现普通递归中的重复计算项，最终达到解决原问题的效果
2、尾递归
如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称之为尾递归（tail recursion）。
- 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文
- 计算的结果在“递”的过程中被保存在参数中，“归”的过程只需层层返回即可
3、动态规划
间接递归
间接递归调用，是函数通过别的函数调用了自己，这一样是递归
只要是递归调用，不管是直接还是间接，都要注意边界问题。但是间接调用有时候是非常不明显的，代码调用复杂时，很难发现出现了递归调用，这是非常危险的。
所以，使用良好的代码规范来避免这种递归的发生。
总结
从本质上看，递归体现了“将问题分解为更小子问题”的思维范式，这种分治策略至关重要。
- 从算法角度看，搜索，排序、回溯、分治、动态规划等许多重要算法策略直接或者间接地应用了这种思维方式
- 从数据结构角度看，递归天然适合处理链表、树和图相关问题，因为它们非常适合用分治思想进行分析。
练习（递归实现）：
- 求n的阶乘
- 将一个数逆序放入列表中，例如1234 → [4, 3, 2, 1]
- 解决猴子吃桃问题：
- 猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想吃时，只剩下一个桃子了。求第一天共摘多少个桃子