Python 递归函数

原文： https://thepythonguru.com/python-recursive-functions/

于 2020 年 1 月 7 日更新

函数本身调用时称为递归。 递归的工作原理类似于循环，但有时使用递归比循环更有意义。 您可以将任何循环转换为递归。

这是递归的工作方式。 递归函数会自行调用。 如您所料，如果不因某种条件而停止，则此过程将无限期重复。 此条件称为基本条件。 每个递归程序中都必须有一个基本条件，否则它将像无限循环一样永远继续执行。

递归函数的工作原理概述：

  1. 递归函数由一些外部代码调用。
  2. 如果满足基本条件，则程序执行有意义的操作并退出。
  3. 否则，函数将执行一些必需的处理，然后调用自身以继续递归。 这是用于计算阶乘的递归函数的示例。

阶乘由数字表示，后跟（!）符号，即4!。

例如：

  1. 4! = 4 * 3 * 2 * 1
  2. 2! = 2 * 1
  3. 0! = 1

这是一个例子

  1. def fact(n):
  2.     if n == 0:
  3.         return 1
  4.     else:
  5.         return n * fact(n-1)
  7. print(fact(0))
  8. print(fact(5))

预期输出：

  1. 1
  2. 120
  1. def fact(n):
  2.     if n == 0:
  3.         return 1
  4.     else:
  5.         return n * fact(n-1)
  7. print(fact(0))
  8. print(fact(5))

现在尝试执行上述函数：

  1. print(fact(2000))

你会得到：

  1. RuntimeError: maximum recursion depth exceeded in comparison

发生这种情况是因为默认情况下 python 在1000调用之后停止了调用递归函数。 若要更改此行为，您需要按如下所示修改代码。

  1. import sys
  2. sys.setrecursionlimit(3000)
  4. def fact(n):
  5.     if n == 0:
  6.         return 1
  7.     else:
  8.         return n * fact(n-1)
  10. print(fact(2000))
  1. import sys
  2. sys.setrecursionlimit(3000)
  4. def fact(n):
  5.     if n == 0:
  6.         return 1
  7.     else:
  8.         return n * fact(n-1)
  10. print(fact(2000))