递归函数python经典例子

递归函数python经典例子

递归函数是一种在函数定义中使用自身的方法。它在编程中被广泛使用，可以解决许多问题。下面将列举一些经典的递归函数示例，以展示其在不同领域的应用。

1. 阶乘函数

阶乘函数是递归函数的典型示例。它用来计算一个非负整数的阶乘。阶乘定义为n! = n * (n-1) * (n-2) * ... * 1，其中0的阶乘定义为1。下面是一个计算阶乘的递归函数示例：

```python

def factorial(n):

if n == 0:

return 1

else:

return n * factorial(n-1)

```

2. 斐波那契数列

斐波那契数列是一个经典的递归函数示例。它是一个无穷序列，每个数字都是前两个数字之和。下面是一个计算斐波那契数列的递归函数示例：

```python def fibonacci(n):

if n <= 1:

return n

else:

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

```

3. 列表求和

列表求和是一个递归函数的常见应用。它递归地将列表中的每个元素相加，直到列表为空。下面是一个计算列表求和的递归函数示例：

```python

def list_sum(lst):

if len(lst) == 0:

return 0

else:

return lst[0] + list_sum(lst[1:])

```

4. 链表反转

链表反转是一个常见的递归问题。它递归地将链表中的每个节点反转，使链表的尾部成为头部，头部成为尾部。下面是一个链表反转的递归函数示例：

```python

class ListNode:

def __init__(self, val=0, next=None):

self.val = val

self.next = next

def reverse_list(head):

if head is None or head.next is None:

return head

else:

new_head = reverse_list(head.next)

head.next.next = head

head.next = None

return new_head

```

5. 二叉树遍历

二叉树遍历是一个常见的递归问题。它递归地遍历二叉树的左子树、根节点和右子树。下面是一个二叉树中序遍历的递归函数示例：

```python

class TreeNode:

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

self.val = val self.left = left

self.right = right

def inorder_traversal(root):

result = []

if root:

result.extend(inorder_traversal(root.left))

result.append(root.val)

result.extend(inorder_traversal(root.right))

return result

```

6. 字符串反转

字符串反转是一个常见的递归问题。它递归地将字符串中的每个字符反转，使字符串的尾部成为头部，头部成为尾部。下面是一个字符串反转的递归函数示例：

```python

def reverse_string(s):

if len(s) <= 1:

return s

else:

return reverse_string(s[1:]) + s[0]

```

7. 图的深度优先遍历

图的深度优先遍历是一个常见的递归问题。它递归地遍历图的每个节点，直到遍历完所有节点。下面是一个图的深度优先遍历的递归函数示例：

```python

def dfs(graph, start, visited=None):

if visited is None:

visited = set()

visited.add(start)

for neighbor in graph[start]:

if neighbor not in visited:

dfs(graph, neighbor, visited)

return visited

```

8. 汉诺塔问题

汉诺塔问题是一个经典的递归问题。它递归地将一堆盘子从一个柱子移动到另一个柱子，遵循某些规则：每次只能移动一个盘子，且大盘子不能放在小盘子上面。下面是一个汉诺塔问题的递归函数示例：

```python def hanoi(n, source, target, auxiliary):

if n > 0:

hanoi(n-1, source, auxiliary, target)

print("Move disk", n, "from", source, "to", target)

hanoi(n-1, auxiliary, target, source)

```

9. 排列组合

排列组合是一个常见的递归问题。它递归地生成给定元素的所有排列组合。下面是一个生成排列组合的递归函数示例：

```python

def permutations(nums):

if len(nums) == 0:

return [[]]

else:

result = []

for i in range(len(nums)):

remaining = nums[:i] + nums[i+1:]

for perm in permutations(remaining):

result.append([nums[i]] + perm)

return result

```

10. 二分搜索

二分搜索是一个常见的递归问题。它递归地在一个有序数组中查找目标元素，通过将数组分成两半并判断目标元素在哪一半中来进行搜索。下面是一个二分搜索的递归函数示例：

```python

def binary_search(nums, target, low, high):

if low > high:

return -1

else:

mid = (low + high) // 2

if nums[mid] == target:

return mid

elif nums[mid] > target:

return binary_search(nums, target, low, mid-1)

else:

return binary_search(nums, target, mid+1, high)

```

以上是一些经典的递归函数示例，它们展示了递归在不同领域的应用。通过理解和学习这些示例，我们可以更好地掌握递归的概念和用法，并将其应用于解决实际问题中。