递归函数需要多少个递归案例和基本案例？

所有递归函数都需要至少一种递归情况和至少一种基本情况。 递归情况是递归函数调用自身的一组情况。 基本情况是递归函数在不调用自身的情况下返回的一组情况。 这是一个简单的递归阶乘函数，具有一个基本情况和一个递归情况：

def factorial(n):
    if n == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        return n * factorial(n - 1)

你打电话时 factorial(5)它返回

如果递归函数的递归情况为零，则它永远不会调用自身并且不是递归函数。 以下错误的阶乘函数有一个基本情况但没有递归情况：

def factorialNoRecursiveCase(n):
  if True:
      # BASE CASE
      return 1

什么时候 factorialNoRecursiveCase(5) 被调用，它返回 1. 问题是，它返回 1 对于每一个论点。

如果递归函数的基数为零，则它永远不会返回，只会递归。 这最终将导致堆栈溢出（除非其他一些。以下错误的阶乘函数具有递归情况但没有基本情况：

def factorialNoBaseCase(n):
  if True:
      # RECURSIVE CASE
      return n * factorialNoBaseCase(n - 1)

什么时候 factorialNoBaseCase(5) 被称为，它会导致 RecursionError: maximum recursion depth exceeded 错误。

正确工作的递归函数还有一个要求：递归函数调用最终必须更接近基本情况。 否则，永远不会达到基本情况，就好像基本情况不存在一样，导致堆栈溢出。 以下错误的阶乘函数有一个递归案例和一个基本案例，但永远不会到达基本案例：

def factorialNoReachBaseCase(n):
    if n == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        return n * factorialNoReachBaseCase(n + 1)  # Adds one instead of subtracts one!

什么时候 factorialNoReachBaseCase(5) 被称为，它永远不会到达基本情况并导致 RecursionError: maximum recursion depth exceeded 错误。

在编写自己的递归函数时，应该问自己三个问题：

什么是基本情况？ 传递给递归函数调用的参数是什么？ 论点是否更接近基本情况？

如果你想了解更多关于递归的知识，请查看我的书，No Starch Press 的 The Recursive Book of Recursion。

阅读更多