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（其中%是取模运算符）递归调用自身，并返回结果。递归继续直到达到基本情况。

示例

这将使用参数24和36调用gcd函数，它将返回它们的最大公约数，即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的数字之和作为参数进行递归调用自身。递归继续直到达到基本情况。

示例

这将使用参数12345调用sum_digits函数，该函数将返回全部数字的和，即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。

递归函数可以是某些类型问题的强大而优雅的解决方案，但如果设计不正确，则可能导致无限递归。重要的是仔细考虑基本情况，并确保函数最终会达到基本情况。