type
status
date
slug
summary
tags
category
icon
password
😏
最近Leetcode的每日一题都是回文串相关的题目，让我回想起之前运用递归的特性对回文进行判断，通过对该方法的运用更好地掌握递归的特性同时更优雅地实现回文判断逻辑。

简介

递归是一种在编程或数学中通过将问题分解为更小、相似的子问题来解决问题的技术。其核心在于函数直接或间接调用自身，通过不断缩小问题规模，直到达到可解的基线条件。 递归分为【递】与【归】两个阶段。【递】指将原始问题分解为若干个规模小、可以用相同的思路来解决的子问题；【归】指当将问题不断缩小的时候，有一个递归出口（临界点/条件），达到这个递归出口，则最小的子问题解决，那么上一层的子问题也解决，以此类推，最终原问题解决。

递归的核心概念

  1. ​基线条件（Base Case）​
      • 递归终止的条件，防止无限调用。例如计算阶乘时，0! = 1 或 1! = 1 是基线条件。
  1. ​递归条件（Recursive Case）​
      • 将原问题分解为更小的子问题。例如 n! = n * (n-1)!，每一步都缩小问题规模。
其实这里类似前面讲到的动态规划中的转移方程及边界条件的确定。
一般而言，递归适用于树/图结构操作、阶乘、斐波那契数列、汉诺塔问题以及快排等算法。但递归算法本身的堆栈特性（后进先出）和自相似性可以在回文链表相关的场景中用于回文判断逻辑的实现。具体而言，回文逻辑的判断满足了以下特性：
  1. 堆栈回溯机制（核心特性）​
      • 递归调用 recursively_check(current_node.next) 会不断深入链表尾部，形成递归堆栈。
      • 当递归触底（current_node 为 None）时，开始逐层回溯。此时，递归堆栈中的 current_node 会从链表尾部向头部逐层返回，而 self.front_pointer 则从头部向尾部移动，二者同步比较值。
  1. ​自相似性
      • 每个递归步骤处理的子问题完全一致：比较当前节点与对称位置的节点值。
      • 无论链表多长，处理逻辑始终是“深入尾部 → 回溯比较 → 移动指针”。
  1. ​基线条件（终止条件）​
      • 当 current_node is None 时，递归终止并开始回溯（返回 True）。
因此可以利用递归算法完成对回文的判断。下面是几道相关的例题：

例题分析

LCR 027.回文链表

给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

思路

利用递归特性，从链表头部开始，不断调用recursively_check(current_node.next)，直到链表末尾（current_node 为 None）。此时递归堆栈保存了所有节点的引用（从头部到尾部），随后从末尾节点开始回溯，每次回溯时：
  • 检查当前尾部节点值 current_node.val 是否等于头部指针 self.front_pointer.val。
  • 若不等，返回 False 并提前终止；若相等，移动 self.front_pointer 到下一个节点。
  • 最终，若所有对称节点值相同，返回 True。

解

该方法的时间复杂度及空间复杂度均为O(n)，笔者在某厂秋招面试过程中，被要求对链表做原地翻转，实现空间复杂度为O(1)的算法。那么这里可以附上快慢指针的解法。核心思想是将链表后半部分进行反转，将前半部分和后半部分进行比较。

LCR 086.分割回文串

给定一个字符串s，请将s分割成一些子串，使每个子串都是回文串 ，返回s所有可能的分割方案。
示例 1：
示例 2：
示例 3：

思路

  1. ​递归与回溯：从字符串的起始位置开始，尝试所有可能的分割点。对于每个分割点，检查其左侧的子串是否为回文。如果是，则递归处理剩余的子串，并将当前分割加入路径。
  1. ​回文判断：通过双指针法快速判断子串是否为回文，避免无效递归。
  1. ​剪枝优化：在递归过程中，仅当当前子串是回文时才继续递归，减少不必要的计算。