C++链表递归函数func的功能与运算逻辑答疑

以下是你询问的函数代码：

class Node{
 public:
 int data;
 Node* next;
};
int func(Node* node, int number){
  if(node){ // 节点非空时继续递归
    if(node->data > 0) // 节点值为正
      return func(node->next, number) - node->data;
    else if(node->data < 0) // 节点值为负
      return func(node->next, number) + node->data;
    else // 节点值为0
      return func(node->next, number + node->data) + number;
 }
 return 0; // 遍历到链表尾部，递归终止
}

对你现有猜想的回应 #

你的两个理解都存在偏差：

• 「函数用后续节点的返回值减去当前节点的data值」只适用于存储正数的节点，存储负数、0的节点运算逻辑并不符合这个描述
• 「函数作用是将链表所有节点的data值设为0」完全错误：整个函数没有任何对node->data的赋值操作，全程只读节点内容，不会修改链表的任何存储数据，最终仅返回一个整数计算结果。

函数实际运行逻辑 #

这个函数采用递归方式遍历单向链表，先一路走到链表末尾（空指针）触发终止条件，再从尾到头逐层回溯计算返回值，规则如下：

• 终止规则：遍历到空指针时直接返回0，开始向上回溯
• 正数节点处理：当前层返回值 = 下一个节点递归返回的结果 - 当前节点的data值，递归时将收到的number参数原封不动传给下一层
• 负数节点处理：当前层返回值 = 下一个节点递归返回的结果 + 当前节点的data值，递归时同样将收到的number参数原封不动传给下一层
• 零值节点处理：当前层返回值 = 下一个节点递归返回的结果 + 当前层收到的number参数；由于node->data为0，递归传给下一层的number值和当前层收到的值完全一致。

运行示例 #

可以通过一个简单测试用例直观理解计算过程：
链表节点顺序为 3 -> -1 -> 0 -> 2，初始调用为func(head, 5)，执行流程：

1. 从head节点开始逐层递归，直到传入空指针，返回0触发回溯
2. 值为2的正数节点：返回 0 - 2 = -2
3. 值为0的节点：返回 -2 + 5 = 3
4. 值为-1的负数节点：返回 3 + (-1) = 2
5. 值为3的正数节点：返回 2 - 3 = -1
   最终函数返回结果为-1。

非0节点的运算可以统一简化理解：每个非0节点都会让最终结果减去自身的绝对值（正数减自身、负数加自身本质都是减绝对值）；每遇到一个值为0的节点，就会在计算结果上额外叠加一次初始调用传入的number值。

内容的提问来源于stack exchange，提问作者Eddy