递归法原理与定义
核心思想
在讨论单链表长度的计算时，递归法提供一种自然的分解方式：将问题化简为子问题，每次沿着链表向后移动一个节点，直到到达尾部为止。通过把当前节点对长度的贡献看作 1，可以把整个长度表示为若干个“1”的累加。
这种思路的核心在于：基准条件（递归结束）和递推关系。当头指针为空时，长度为 0；否则长度等于头结点贡献1再加上后续子链表的长度。
递归基准与递推关系
基准条件是 head 为空，此时返回 0，表示空链表的长度为零。递推关系是 length(head) = 1 + length(head->next)，这确保每向后移动一个节点，累加一次。
在实现时，递归深度等同于链表长度，这意味着长链表会带来较深的栈调用层级，需要关注栈溢出风险。
实现细节与边界条件
头结点与空链表处理
实现时需要对头指针进行判断。空链表直接返回0，避免对空指针进行解引用。
对于非空链表，函数头部检查后向后调用自身，确保每次递归调用只处理当前节点，而不是整条链表。
递归边界与返回值
返回值的设计应确保返回值类型足以容纳链表的最大长度。常见实现中使用整型，若链表极大可能需使用长整型。
考虑到栈空间，递归深度限制是需要关注的系统行为，在极端场景下可能需要改用迭代实现。
代码实现示例（C++）
数据结构与入口函数
下面给出一个简洁的单链表节点定义以及入口函数的雏形，重点演示如何从头结点进行递归计算。结构体节点的定义应简单明了，包含至少一个指向下一个节点的指针。
通过在入口处对 head 进行判断，可以把空链表情况放在最前面处理，避免额外的边界判断。
递归函数实现
递归函数的核心在于一个简单的终止条件与简单的再递推，这使得代码可读性很高。请注意，递归深度等于链表长度，因此对于极长的链表，可能出现栈溢出风险。
// C++ 递归求单链表长度的示例
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};int length_recursive(ListNode* head) {if (head == nullptr) return 0; // 基准条件：空链表return 1 + length_recursive(head->next); // 递推关系：当前节点贡献1，加上后续长度
}// 示例：构建链表并调用
#include <iostream>
int main() {ListNode* n3 = new ListNode(3);ListNode* n2 = new ListNode(2); n2->next = n3;ListNode* n1 = new ListNode(1); n1->next = n2;int len = length_recursive(n1);std::cout << "长度: " << len << std::endl;return 0;
}
时间复杂度分析
时间复杂度推导
该递归实现在每个节点上做一个常数操作并调用下一节点，T(n) = T(n-1) + O(1)，因此时间复杂度为 O(n)，其中 n 是链表长度。
由于递归调用要打开一个新的栈帧，递归深度等于链表长度，时间开销与栈的管理也共同存在。
空间复杂度与栈帧
空间复杂度主要来自递归栈，最坏情况下的空间复杂度为 O(n)，与链表长度成正比。若优化为迭代实现，可以将空间复杂度降至 O(1)。
性能对比与注意点
与迭代法对比
与迭代法相比，递归法实现直观简单，但栈深度可能造成栈溢出，在极长的链表上需要谨慎使用。
迭代法通过遍历链表并计数，可以在同一时间达到 O(1)额外空间，但代码略显冗长且易错。
实际开发中的选择
在资源受限的嵌入式场景，优先考虑迭代实现；在教学或原型阶段，递归实现有助于理解链表结构与递归思维。
