如何在 Python 中创建递归函数？

---

递归是一种编程技巧，其中函数在其主体中调用自身一次或多次。通常，它会返回此函数调用的返回值。如果函数定义遵循递归，我们称此函数为递归函数。

一个递归函数必须在程序中使用之前终止。如果每次递归调用，问题的解决都变得更小并朝着基本情况发展，则它会终止，在基本情况中，可以无需进一步递归即可解决问题。如果在调用中不满足基本情况，递归会导致无限循环。

我们使用 Python 中的递归函数来解决现实世界的数学问题。

前 n 个自然数之和

以下代码使用递归 Python 函数返回前 n 个自然数之和。

示例

这将打印前 100 个自然数和前 500 个自然数的和

def sum_n(n):
   if n== 0:
       return 0 
   else:
      return n + sum_n(n-1)
print(sum_n(100)) 
print(sum_n(500))

输出

5050
125250

使用递归的阶乘函数

递归函数是指重复调用自身直到达到停止递归的基本情况的函数。让我们考虑一个 Python 中简单递归函数的示例，该函数计算给定数字的阶乘

在这里，阶乘函数采用正整数 n 作为参数，并返回该数字的阶乘。如果 n 等于 0，则函数返回 1，这是基本情况。否则，函数会递归调用自身，参数为 n-1，并将结果乘以 n。递归将持续进行，直到达到基本情况。

示例

这将调用阶乘函数，参数为 5，它将返回 5 * 4 * 3 * 2 * 1 = 120。

def factorial(n):
   if n == 0:
      return 1 
   else:
      return n * factorial(n-1)
print(factorial(5))

输出

120

使用递归的斐波那契数列

在此示例中，斐波那契函数采用非负整数 n 作为参数，并返回斐波那契数列中的第 n 个数。如果 n 等于 0，则函数返回 0。如果 n 等于 1，则函数返回 1。否则，函数会递归调用自身，参数为 n-1 和 n-2，并返回结果之和。递归将持续进行，直到达到基本情况。

示例

这将调用斐波那契函数，参数为 6，它将返回斐波那契数列中的第 6 个数，即 8。

def fibonacci(n):
   if n == 0:
      return 0 
   elif n == 1:
      return 1
   else:
      return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(6))

输出

8

如何查找数字的最大公约数

Python 中另一个查找两个正整数的最大公约数 (GCD) 的递归函数示例如下

在此示例中，gcd 函数采用两个正整数 a 和 b 作为参数，并返回它们的最大公约数。如果 b 等于 0，则函数返回 a，这是基本情况。否则，函数会递归调用自身，参数为 b 和 a % b，其中 % 是模运算符，并返回结果。递归将持续进行，直到达到基本情况。

示例

这将调用 gcd 函数，参数为 24 和 36，它将返回它们的最大公约数，即 12。

def gcd(a, b):
   if b == 0:
      return a 
   else:
       return gcd(b, a % b) 
print(gcd(24, 36))

输出

12

计算正整数的数字之和

在此示例中，sum_digits 函数采用正整数 n 作为参数，并返回其数字之和。如果 n 小于 10，则函数返回 n，这是基本情况。否则，函数将 n 的最后一位数字添加到使用整数除法 (// 运算符) 将 n 除以 10 得到的数字之和中，并使用结果递归调用自身。递归将持续进行，直到达到基本情况。

示例

这将调用 sum_digits 函数，参数为 12345，它将返回其数字之和，即 1 + 2 + 3 + 4 + 5 = 15。

def sum_digits(n):
   if n < 10:
      return n
   else:
      return n % 10 + sum_digits(n // 10) 
print(sum_digits(12345))

输出

15

查找字符串的长度

在此示例中，string_length 函数采用字符串 s 作为参数，并返回其长度。如果 s 是空字符串 (''), 则函数返回 0，这是基本情况。否则，函数将 1 添加到通过切片第一个字符 (s[0]) 并使用剩余字符串 (s[1:]) 递归调用 string_length 函数获得的字符串长度中。递归将持续进行，直到达到基本情况。

示例

def string_length(s):
   if s == '':
      return 0
   else:
      return 1 + string_length(s[1:])
print(string_length('hello world'))

输出

11

这将调用 string_length 函数，参数为 'hello world'，它将返回其长度，即 11。

递归函数可以为某些类型的问题提供强大而优雅的解决方案，但如果设计不当，它们也可能导致无限递归。务必仔细考虑基本情况并确保函数最终会达到它。