Python 算法之递归与尾递归，斐波那契数列以及汉诺塔的实现
内容提要
本文介绍了Python中的递归和尾递归，包括递归的基本概念、要素及其与迭代的区别。通过阶乘、斐波那契数列和汉诺塔问题的示例，展示了递归的实现方式。讨论了尾递归的定义及其优化方法，指出Python不支持尾递归优化，但可以通过特定装饰器实现。
延伸解读
递归与迭代的思维差异
文章指出递归是从后向前计算，迭代是从前向后计算。这反映了两种不同的解题思路：递归将问题分解为更小的同类问题，直到基本出口，再逐层返回结果；迭代则从初始状态出发，重复执行相同步骤逐步逼近目标。理解这一差异有助于在编程中选择合适的实现方式，例如阶乘既可用递归也可用循环实现。
斐波那契递归的性能陷阱与优化
文章中的斐波那契递归实现时间复杂度为O(2^n)，稍大的n就会导致计算时间过长。为此，文章提供了两种优化方案：使用lru_cache缓存中间结果，或改写为尾递归形式传递累积参数。前者以空间换时间，后者则更节省时间和空间。读者在实际应用中应避免直接使用朴素递归计算较大的斐波那契数。
Python尾递归优化的限制与变通
文章明确指出Python不支持尾递归优化，普通递归深度过大时会引发RecursionError。对于深度不大的情况，可以调整sys.setrecursionlimit；若深度非常大，则可采用tail_call_optimized装饰器。该装饰器通过异常机制销毁递归栈，使递归过程中只保留一个栈帧，从而模拟尾递归优化。但需注意，此方案并非官方支持，且要求递归调用必须处于尾位置。
Q&A
什么是递归？
递归是程序调用自身的编程技巧，通常将复杂问题转化为规模较小的问题求解。
递归与迭代有什么区别？
递归是从后向前计算，而迭代是从前向后计算。
如何用递归实现阶乘？
阶乘的递归定义为 n! = n * (n-1)!，基本出口为 n == 0 时返回 1。
斐波那契数列的递归实现是什么？
斐波那契数列的递归定义为 F(n) = F(n-1) + F(n-2)，基本出口为 n == 1 或 n == 2 时返回 1。
汉诺塔问题如何用递归解决？
汉诺塔问题通过递归将 n-1 个盘子移动到辅助柱子，再移动最后一个盘子，最后将 n-1 个盘子移动到目标柱子。
什么是尾递归？
尾递归是指递归调用出现在函数的末尾，避免了新局部变量的产生，类似于迭代。
