技术文摘
Python 中 15 个递归函数经典实例剖析
2024-12-30 16:17:34 小编
Python 中 15 个递归函数经典实例剖析
在 Python 编程中,递归函数是一种强大而富有挑战性的概念。它通过在函数内部调用自身来解决问题,能够简洁地处理一些复杂的逻辑。以下为您详细剖析 15 个经典的递归函数实例。
实例 1:计算阶乘
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
实例 2:斐波那契数列
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
实例 3:计算列表元素之和
def list_sum(lst):
if not lst:
return 0
else:
return lst[0] + list_sum(lst[1:])
实例 4:反转字符串
def reverse_string(s):
if len(s) == 0:
return s
else:
return reverse_string(s[1:]) + s[0]
实例 5:计算二叉树节点个数
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def count_nodes(root):
if root is None:
return 0
else:
return 1 + count_nodes(root.left) + count_nodes(root.right)
实例 6:求最大公约数
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
实例 7:汉诺塔问题
def hanoi(n, src, aux, dest):
if n == 1:
print(f"Move disk 1 from {src} to {dest}")
return
hanoi(n - 1, src, dest, aux)
print(f"Move disk {n} from {src} to {dest}")
hanoi(n - 1, aux, src, dest)
实例 8:生成全排列
def permute(lst):
if len(lst) == 0:
return []
if len(lst) == 1:
return [lst]
result = []
for i in range(len(lst)):
m = lst[i]
rem_lst = lst[:i] + lst[i + 1:]
for p in permute(rem_lst):
result.append([m] + p)
return result
实例 9:判断回文
def is_palindrome(s):
if len(s) <= 1:
return True
if s[0]!= s[-1]:
return False
return is_palindrome(s[1:-1])
实例 10:数字转换为字符串
def num_to_str(n):
if n < 10:
return str(n)
else:
return num_to_str(n // 10) + str(n % 10)
实例 11:求数组最大值
def max_in_list(lst):
if len(lst) == 1:
return lst[0]
else:
return max(lst[0], max_in_list(lst[1:]))
实例 12:计算指数
def power(base, exp):
if exp == 0:
return 1
else:
return base * power(base, exp - 1)
实例 13:生成杨辉三角
def pascal_triangle(n):
if n == 0:
return [1]
else:
prev_row = pascal_triangle(n - 1)
new_row = [1]
for i in range(len(prev_row) - 1):
new_row.append(prev_row[i] + prev_row[i + 1])
new_row.append(1)
return new_row
实例 14:合并排序
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left_half = merge_sort(lst[:mid])
right_half = merge_sort(lst[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
实例 15:快速排序
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[len(lst) // 2]
less = [x for x in lst if x < pivot]
greater = [x for x in lst if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
通过对这 15 个经典递归函数实例的剖析,相信您对 Python 中的递归函数有了更深入的理解和掌握。在实际编程中,合理运用递归函数可以使代码更加简洁高效,但也要注意递归的深度和性能问题,避免出现栈溢出等错误。
- 微服务架构中的关键注册中心
- Spring Boot 应用的零停机更新策略
- Java 基础中常被忽视的 this:实战技巧全面解析
- 大促系统中应用启动速度的优化实践
- 得物商家客服从 Electron 迁移至 Tauri 的技术实践
- 深入解析 Go 并发:上下文传播与取消的机密
- Vue.js 开发技巧:懒加载组件与直接导入的抉择时机
- Python 递归的十大技巧秘籍
- Python 元组:解构、打包与解包的技巧探秘
- 解析 Go 协程调度的实质
- 代码杂乱无章?此模式助你一键规整!
- Matplotlib 库使用基础解析
- 责任链模式是什么?如何将责任串成链?
- 单例的五种手撕写法
- C# 构建事件总线:高效管理事件 优化代码风格