Python基础之递归函数

什么是递归函数？

递归函数是指在函数定义中包含对函数本身的调用的函数，这种函数也被称为递归函数。

递归函数在循环和条件语句无法很好地解决问题时非常有用。例如，当解决涉及到树状结构或分治问题时，递归函数非常适用。

递归函数的特点

递归函数有以下特点：

• 函数在定义中调用自己。
• 递归函数需要有一个停止条件，避免形成无限循环。
• 递归函数可以有多个递归调用。

递归函数的使用

下面通过两个示例介绍递归函数的使用。

示例1：计算阶乘

阶乘是指一个非负整数$n$的阶乘，表示为$n!$等于$n$乘以$n-1$乘以$n-2$……1。特别的，$0!=1$。阶乘是一个非常典型的递归问题。

以下是计算阶乘的递归函数：

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

在这个函数中，当$n=0$时，函数返回$1$，否则函数返回$n$和$factorial(n-1)$的乘积。

接下来，我们调用这个函数：

print(factorial(5)) # 5 * 4 * 3 * 2 * 1 = 120

输出：

120

示例2：二分查找

假设我们有一个有序数组arr和要查找的元素x，现在需要在这个数组中查找元素x的位置。二分查找是一种典型的使用递归实现的算法。

以下是二分查找的递归函数：

def binary_search(arr, x, low, high):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, x, low, mid-1)
        else:
            return binary_search(arr, x, mid+1, high)
    else:
        return -1

在这个函数中，我们首先检查$high$是否大于或等于$low$。如果不是，则返回-1，表示没有找到指定元素；如果是，则按如下步骤继续查找：

• 找到数组中央的元素的下标$mid$（用Python的整数除法符号$//$可以向下取整）。
• 如果中央元素等于要查找的元素$x$，则返回中央元素下标$mid$。
• 如果中央元素大于要查找的元素$x$，则递归地调用$binary_search$函数在数组的左半部分继续查找。
• 如果中央元素小于要查找的元素$x$，则递归地调用$binary_search$函数在数组的右半部分继续查找。

接下来，我们调用这个函数：

arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x, 0, len(arr)-1)

if result != -1:
    print("元素在数组中的下标为", result)
else:
    print("元素不在数组中")

输出：

元素在数组中的下标为 3

总结

递归函数是一种在函数定义中包含对函数本身的调用的函数。递归的应用范围很广，例如计算阶乘、二分查找等等。需要注意的是，递归函数需要有一个停止条件，避免形成无限循环。