链表递归：递推关系确认与递归树构建求助

Hey there! Awesome call on getting the recurrence relation right—you’re already halfway there. Let’s walk through how to build and analyze the recursion tree for your linked list length-counting recursive function.

First, Let’s Confirm the Recurrence Relation #

First, let’s anchor this with a full example of the recursive length code (since you mentioned you’ve already written it):

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int Length(Node* head) {
    // Base case: empty list has length 0
    if (head == NULL) {
        return 0;
    }
    // Recursive case: count current node + length of remaining list
    return 1 + Length(head->next);
}

Your recurrence relation T(n) = T(n-1) + O(1) is 100% correct. Here’s why:

• T(n) represents the time to process a linked list with n nodes.
• Base case: T(0) = O(1) (we just check if head is NULL and return 0—constant time).
• Recursive case: For a list with n nodes, we do constant-time work (check head isn’t NULL, add 1 to the result) then recursively process the sublist of n-1 nodes. Hence T(n) = T(n-1) + O(1).

Building the Recursion Tree #

A recursion tree visualizes each recursive call as a node, with edges pointing to the calls it spawns. For this function, since each call only makes one recursive sub-call, the tree is a straight linear chain (no branching). Here’s how to construct it step by step:

1. Root Node: Start with the top-level call to process n nodes. This node has a constant-time cost (O(1)) for the non-recursive work (checking head, adding 1). It has exactly one child node: the call to process n-1 nodes.
2. Next Level: The node for n-1 nodes also has a constant-time cost (O(1)), and one child node for n-2 nodes.
3. Repeat: Keep this going until you reach the base case: a node for 0 nodes (empty list). This node has a constant-time cost (O(1)) and no child nodes (since we hit the base case and stop recursing).

Textual Representation of the Recursion Tree #

Level 0: [n nodes] → Cost: O(1)
          ↓
Level 1: [n-1 nodes] → Cost: O(1)
          ↓
Level 2: [n-2 nodes] → Cost: O(1)
          ↓
          ...
          ↓
Level n: [0 nodes] → Cost: O(1)

Analyzing the Recursion Tree #

To find the total time complexity, sum up the costs across all levels:

• The tree has n+1 levels (from level 0 to level n).
• Each level contributes exactly O(1) cost.
• Total cost = (n+1) * O(1) = O(n)

This matches the result you’d get by expanding the recurrence relation:
T(n) = T(n-1) + c = T(n-2) + 2c = ... = T(0) + nc = 0 + nc = O(n) (where c is the constant time per call).

Key Note #

Unlike divide-and-conquer algorithms (like merge sort) that have branching recursion trees, this tree is a linear chain because each recursive call only spawns one sub-call. That’s directly tied to the structure of a singly linked list—you can only traverse forward one node at a time, so recursion follows that linear path.

Hope this makes building and interpreting the recursion tree clear! Let me know if you want to dig into any edge cases or further details.

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