递归移除相邻重复字符是字符串处理中常见的算法场景，很多开发者第一眼看到递归的实现方式，会下意识认为每次递归都需要遍历整个字符串，从而得出时间复杂度为O(n²)的结论，但实际上这个算法的时间复杂度是O(n)，下面我们来详细分析其中的原因。
递归移除相邻重复字符的基本实现
我们先来看递归移除相邻重复字符的基础实现逻辑：遍历字符串，找到第一对相邻的重复字符，删除这两个字符后，对剩下的字符串递归执行同样的操作，直到字符串中不存在相邻重复字符为止。
下面是Python语言的基础实现代码：
def remove_adjacent_duplicates(s):
# 遍历字符串查找相邻重复字符
for i in range(len(s) - 1):
if s[i] == s[i + 1]:
# 找到后删除这两个字符，递归处理剩余部分
return remove_adjacent_duplicates(s[:i] + s[i+2:])
# 没有相邻重复字符时返回原字符串
return s
# 测试示例
test_str = "abbaca"
result = remove_adjacent_duplicates(test_str)
print(result) # 输出ca
错误的时间复杂度分析思路
很多人认为这个算法的时间复杂度是O(n²)，推导逻辑通常是这样的：每次递归调用都需要遍历整个当前字符串，字符串长度从n逐渐减小到1，总操作次数是n + (n-1) + (n-2) + ... + 1，求和后得到n(n+1)/2，也就是O(n²)。
但这个推导的问题在于，它默认每次递归都会遍历整个当前字符串，实际上递归过程中并不会重复遍历已经处理过的字符。
正确的O(n)时间复杂度分析
我们可以从字符的访问次数角度来分析：每个字符在整个递归过程中最多只会被访问一次，访问的场景只有两种，一是在查找相邻重复字符时被检查，二是被删除后不再参与后续处理。
我们可以用一个具体的例子来拆解执行过程，比如输入字符串是"abbaca"：
- 第一次遍历"abbaca"，检查到索引1和2的字符都是b，删除这两个b，剩余字符串是"aaca"，递归处理"aaca"
- 遍历"aaca"，检查到索引0和1的字符都是a，删除这两个a，剩余字符串是"ca"，递归处理"ca"
- 遍历"ca"，没有相邻重复字符，返回结果"ca"
整个过程中，每个字符只被检查了一次，没有重复遍历的情况，因此总操作次数是O(n)，时间复杂度为O(n)。
用栈优化后的实现验证
递归的实现本质上和用栈处理相邻重复字符的逻辑是一致的，栈实现的代码可以更直观地体现O(n)的时间复杂度：
def remove_adjacent_duplicates_stack(s):
stack = []
for char in s:
# 栈顶元素和当前字符相同，弹出栈顶元素，相当于删除相邻重复字符
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return ''.join(stack)
# 测试示例
test_str = "abbaca"
result = remove_adjacent_duplicates_stack(test_str)
print(result) # 输出ca
栈的实现中，每个字符只会入栈和出栈各一次，总操作次数是O(n)，和递归实现的时间复杂度一致，这也验证了递归实现的时间复杂度确实是O(n)。
总结
递归移除相邻重复字符的算法之所以时间复杂度是O(n)而不是O(n²)，核心原因是每个字符在整个递归过程中只会被访问一次，不会出现重复遍历的情况。分析递归算法的时间复杂度时，不能只看递归的调用次数，还要结合每次递归的实际操作范围，避免陷入默认每次递归都遍历全量的误区。