python递归算法经典实例

Python递归算法经典实例有很多，以下是其中几个比较经典的例子：

1. 阶乘函数：计算一个正整数的阶乘，可以使用递归算法。例如，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

2. 斐波那契数列：计算斐波那契数列的第n项，可以使用递归算法。斐波那契数列定义为：f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2)。

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 输出 55

3. 二叉树遍历：遍历二叉树可以使用递归算法。比如，先序遍历可以先访问根节点，再遍历左子树和右子树；中序遍历可以先遍历左子树，再访问根节点，最后遍历右子树；后序遍历可以先遍历左子树和右子树，最后访问根节点。

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 先序遍历
def preorderTraversal(root):
    if root is None:
        return []
    else:
        return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)

# 中序遍历
def inorderTraversal(root):
    if root is None:
        return []
    else:
        return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)

# 后序遍历
def postorderTraversal(root):
    if root is None:
        return []
    else:
        return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]

# 构建一棵二叉树
root = TreeNode(1, TreeNode(2), TreeNode(3))

# 测试遍历函数
print(preorderTraversal(root))  # 输出 [1, 2, 3]
print(inorderTraversal(root))  # 输出 [2, 1, 3]
print(postorderTraversal(root))  # 输出 [2, 3, 1]

这些例子展示了递归算法的用法，但是需要注意递归算法的缺点，比如递归深度过深可能会导致调用栈溢出，而且递归算法的效率也不如迭代算法。因此，在实际应用中，需要根据具体情况选择使用递归算法还是迭代算法。