原文： https://pythonspot.com/recursion/

在英语中，有许多递归示例：

  • “要了解递归，您必须先了解递归”，
  • “人就是人的母亲”。

您可能想知道，这与编程有什么关系？

您可能需要将一个复杂的问题分解为几个较小的问题。 您已经熟悉循环或迭代。 在某些情况下，递归可能是更好的解决方案。

在 Python 中，如果函数调用自身并且具有终止条件，则该函数是递归的。 为什么要终止条件？ 阻止函数无限自我调用。

递归示例

列表中的递归

让我们从一个非常基本的示例开始：将所有数字添加到列表中。 如果没有递归，则可能是：

  1. #!/usr/bin/env python
  3. def sum(list):
  4.     sum = 0
  6.     # Add every number in the list.
  7.     for i in range(0, len(list)):
  8.         sum = sum + list[i]
  10.     # Return the sum.
  11.     return sum
  13. print(sum([5,7,3,8,10]))

在我们简单地调用sum函数的地方，该函数将每个元素添加到变量sum并返回。 递归执行此操作：

  1. #!/usr/bin/env python
  3. def sum(list):
  4.     if len(list) == 1:
  5.         return list[0]
  6.     else:
  7.         return list[0] + sum(list[1:])
  9. print(sum([5,7,3,8,10]))

如果列表的长度为 1，则返回列表（终止条件）。 否则，它返回元素，并调用函数sum()减去列表中的一个元素。 如果执行了所有调用，则返回达到终止条件并返回应答。

递归阶乘

阶乘的数学定义是：n! = n * (n-1)!,如果n > 1并且f(1) = 1。示例：3! = 3 x 2 x 1 = 6。我们可以使用递归函数在 Python 中实现：

  1. #!/usr/bin/env python
  3. def factorial(n):
  4.     if n == 1:
  5.         return 1
  6.     else:
  7.         return n * factorial(n-1)
  9. print(factorial(3))

调用阶乘函数n = 3时。它将返回n * factorial(n-1)。 该过程将一直持续到n = 1。如果达到n == 1，它将返回结果。

递归限制

每次函数调用自身并存储一些内存。 因此，与传统函数相比，递归函数可以容纳更多的内存。 Python 在 1000 次调用的深度后停止函数调用。 如果运行此示例：

  1. #!/usr/bin/env python
  3. def factorial(n):
  4.     if n == 1:
  5.         return 1
  6.     else:
  7.         return n * factorial(n-1)
  9. print(factorial(3000))

您将收到错误：

  1. RuntimeError: maximum recursion depth exceeded

在其他编程语言中，您的程序可能会崩溃。 您可以通过修改递归调用的数量来解决此问题，例如：

  1. #!/usr/bin/env python
  2. import sys
  4. sys.setrecursionlimit(5000)
  6. def factorial(n):
  7.     if n == 1:
  8.         return 1
  9.     else:
  10.         return n * factorial(n-1)
  12. print(factorial(3000))

但是请记住，阶乘函数的输入仍然有限制。 因此，您应该明智地使用递归。 正如您现在对阶乘问题所了解的那样，递归函数并不是最佳解决方案。 对于其他问题（例如遍历目录），递归可能是一个很好的解决方案。