当前位置：首页 > news >正文

递归函数，数学表达式转化成递归函数

news 2025/5/29 17:45:53

一、识别递归结构

什么是递归，其核心思想是什么

递归是一个函数直接或间接地调用自身的操作方式。
核心思想：递归通常用于把一个复杂的大问题分解成一个或几个相同结构的小问题，直到问题小到可以直接解决。

递归的过程

不断拆解问题（递去）：把问题越分越小。
触底反弹（归来）：遇到最小问题时开始返回结果。

递归的必备条件（如果不满足的话，可能会导致无限循环或栈溢出）

终止条件（Base Case）
明确递归何时结束，防止无限调用。
递归调用（Recursive Case）
问题必须能分解为结构相同的子问题。
向终止条件逼近
每次递归调用必须是问题规模减小（从n次变成n-1次，知道最底层的基准条件）。

递归适用于什么场景

问题本身可以分解成相同结构的子问题（数学归纳法得到的公式）
例如：计算阶乘（1×2×3×…×(n-1)×n）

def factorial(n):if n == 0:  # 终止条件：0! = 1return 1return n * factorial(n - 1)  # 递归调用：n! = n × (n-1)!

这个函数的执行过程：

	factorial(3) = 3 × factorial(2)  = 3 × (2 × factorial(1))  = 3 × (2 × (1 × factorial(0)))  = 3 × (2 × (1 × 1))  = 6

数据本身是递归定义的问题（链表、树）
例如遍历二叉树

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef traverse(root):if root is None:  # 终止条件：空节点returntraverse(root.left)   # 递归左子树print(root.val)      # 访问当前节点traverse(root.right)  # 递归右子树

遍历二叉树的执行过程：

	      1/ \2   3/ \4   5遍历顺序：4 → 2 → 5 → 1 → 3

需要回溯或组合尝试所有可能的问题（排序问题）

二、将数学表达式转化为递归函数

将数学表达式转化为递归函数需要理解递归的两个关键要素：基准条件和递归关系。以下是系统化的转换方法：

步骤1：原始的数学表达式

	1/(1×2) - 1/(2×3) + 1/(3×4) - 1/(4×5) + ... ± 1/(n×(n+1))

步骤2：定义通项公式
观察到第k项为：

	f(k) = (-1)^(k+1) × 1/(k×(k+1))

步骤3：建立 n 和 n-1 项的递推关系

	S(n) = f(1) ± f(2) ± ... ± f(n)S(n) = S(n-1) ± f(n)S(n) = S(n-1) + (-1)^(n+1) × 1/(n×(n+1))

步骤4：确定基准条件（最初的状态）

	S(0) = 0S(1) = 1/2

步骤5：处理符号交替（有些简单的函数的处理可能没有这一步）
通过奇偶判断实现符号交替：

if n % 2 == 0:  # 偶数项为负return S(n-1) - term
else:           # 奇数项为正return S(n-1) + term

步骤6：将以上步骤转化为函数形式

def recursive_sum(n):# 基准条件if n == 0:return 0elif n == 1:return first_term_value# 计算当前项current_term = calculate_term(n)# 递归关系（根据符号规则调整+-）if is_positive_term(n):return recursive_sum(n-1) + current_termelse:return recursive_sum(n-1) - current_term

处理的关键点

项数处理：递归参数n通常表示项数而非下标
符号处理：通过(-1)^n或奇偶判断实现符号交替
计算效率：注意Python默认递归深度限制（约1000层）

其他示例练习：斐波那契数列

数学定义：

1、确定基准：F(0)=0, F(1)=1
2、确定第n项的公式：F(n)=F(n-1)+F(n-2)
3、确定前n项和与前n-1项和的关系：S(n)=S(n-1)+F(n)
4、注意观察是否需要符号转换，也就是数学公式里是否有(-1)^n

尝试自己实现斐波那契数列的第n项和前n项和的递归实现：

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