递归函数python经典例子

2024年1月31日发(作者：)

递归函数python经典例子

递归函数是一种非常重要的编程技巧，它可以让我们在编写程序时更加高效和简洁。在Python中，递归函数的使用非常广泛，下面我们来看一些经典的例子。

1. 阶乘函数

阶乘函数是递归函数的经典例子之一。它的定义如下：

```

def factorial(n):

if n == 0:

return 1

else:

return n * factorial(n-1)

```

这个函数的作用是计算n的阶乘。当n等于0时，返回1；否则，返回n乘以n-1的阶乘。

2. 斐波那契数列

斐波那契数列也是递归函数的经典例子之一。它的定义如下：

```

def fibonacci(n):

if n == 0:

return 0

elif n == 1:

return 1

else:

return fibonacci(n-1) + fibonacci(n-2)

```

这个函数的作用是计算斐波那契数列的第n项。当n等于0时，返回0；当n等于1时，返回1；否则，返回斐波那契数列的第n-1项和第n-2项的和。

3. 汉诺塔问题

汉诺塔问题也是递归函数的经典例子之一。它的定义如下：

```

def hanoi(n, A, B, C):

if n == 1:

print(A, "->", C)

else:

hanoi(n-1, A, C, B)

print(A, "->", C)

hanoi(n-1, B, A, C)

```

这个函数的作用是解决汉诺塔问题。当n等于1时，直接将A柱子上的盘子移动到C柱子上；否则，先将A柱子上的n-1个盘子移动到B柱子上，然后将A柱子上的最后一个盘子移动到C柱子上，最后将B柱子上的n-1个盘子移动到C柱子上。

4. 二分查找

二分查找也是递归函数的经典例子之一。它的定义如下：

```

def binary_search(arr, low, high, x):

if high >= low:

mid = (high + low) // 2

if arr[mid] == x:

return mid

elif arr[mid] > x:

return binary_search(arr, low, mid-1, x)

else:

return binary_search(arr, mid+1, high, x)

else:

return -1

```

这个函数的作用是在有序数组arr中查找元素x。如果找到了，返回元素的下标；否则，返回-1。函数使用了递归的方式，每次将数组分成两半，然后在其中一半中查找元素x。

5. 快速排序

快速排序也是递归函数的经典例子之一。它的定义如下：

```

def quick_sort(arr):

if len(arr) <= 1:

return arr

else:

pivot = arr[0]

left = [x for x in arr[1:] if x < pivot]

right = [x for x in arr[1:] if x >= pivot]

return quick_sort(left) + [pivot] + quick_sort(right)

```

这个函数的作用是对数组arr进行快速排序。函数使用了递归的方式，每次选择一个基准元素，将数组分成两部分，然后对每一部分进行快速排序。

6. 树的遍历

树的遍历也是递归函数的经典例子之一。它的定义如下：

```

class TreeNode:

def __init__(self, val=0, left=None, right=None):

= val

= left

= right

def preorder_traversal(root):

if root:

print()

preorder_traversal()

preorder_traversal()

def inorder_traversal(root):

if root:

inorder_traversal()

print()

inorder_traversal()

def postorder_traversal(root):

if root:

postorder_traversal()

postorder_traversal()

print()

```

这个函数的作用是对树进行前序遍历、中序遍历和后序遍历。函数使用了递归的方式，每次先遍历根节点，然后遍历左子树和右子树。

7. 判断回文字符串

判断回文字符串也是递归函数的经典例子之一。它的定义如下：

```

def is_palindrome(s):

if len(s) <= 1:

return True

else:

return s[0] == s[-1] and is_palindrome(s[1:-1])

```

这个函数的作用是判断字符串s是否是回文字符串。函数使用了递归的方式，每次判断字符串的第一个字符和最后一个字符是否相等，然后递归判断去掉第一个和最后一个字符的子串是否是回文字符串。

8. 求最大公约数

求最大公约数也是递归函数的经典例子之一。它的定义如下：

```

def gcd(a, b):

if b == 0:

return a

else:

return gcd(b, a % b)

```

这个函数的作用是求a和b的最大公约数。函数使用了递归的方式，每次将b和a%b作为参数递归调用函数，直到b等于0。

9. 求幂函数

求幂函数也是递归函数的经典例子之一。它的定义如下：

```

def power(x, n):

if n == 0:

return 1

elif n % 2 == 0:

return power(x*x, n//2)

else:

return x * power(x*x, n//2)

```

这个函数的作用是求x的n次幂。函数使用了递归的方式，每次将n除以2，然后递归调用函数，直到n等于0或1。

10. 求组合数

求组合数也是递归函数的经典例子之一。它的定义如下：

```

def combination(n, k):

if k == 0 or k == n:

return 1

else:

return combination(n-1, k-1) + combination(n-1, k)

```

这个函数的作用是求从n个元素中选取k个元素的组合数。函数使用了递归的方式，每次将问题转化为从n-1个元素中选取k-1个元素和从n-1个元素中选取k个元素的组合数之和。