COMP2521 Week 2 - Recursion & Linked Lists

🔄 What is Recursion? 🔄 什么是递归？

Recursion is when a function calls itself to solve a smaller version of the same problem. 递归是指一个函数调用自身来解决同一问题的更小版本。

⚡ Every recursive function needs TWO things: ⚡ 每个递归函数都需要两件事：

Base Case基础情况 — when to STOP recursing — 什么时候停止递归
Recursive Case递归情况 — call yourself with a SMALLER problem — 用更小的问题调用自己

⚠️ Without a base case → infinite recursion → stack overflow crash! 没有基础情况 → 无限递归 → 栈溢出崩溃！

Recursion Template 递归模板

int myFunc(int n) {
    // 1. Base case: when to stop
    if (n == 0) {
        return someValue;
    }

    // 2. Recursive case: smaller problem
    return myFunc(n - 1) + something;
}

📐 Task 1: GCD (Euclid's Algorithm) 📐 任务 1：GCD（欧几里得算法）

The Greatest Common Divisor (GCD) of two integers is the largest number that divides both with no remainder. 最大公因数（GCD）是能整除两个整数的最大数。

💡 Euclid's Key Identity: 💡 欧几里得核心公式：

gcd(a, b) = gcd(b, a % b)

Keep applying this until the remainder is 0. The other number is the GCD. 不断应用直到余数为 0，另一个数就是 GCD。

Step-by-step Example: gcd(16, 28) 逐步示例：gcd(16, 28)

gcd(16, 28) → gcd(28, 16) [swap so larger is first... actually order doesn't matter] → gcd(16, 12) [28 % 16 = 12] → gcd(12, 4) [16 % 12 = 4] → gcd(4, 0) [12 % 4 = 0] → return 4 ✓ [base case: b == 0]

Implementation 实现代码

int gcd(int a, int b) {
    // Base case: if b is 0, GCD is a
    if (b == 0) {
        return a;
    }
    // Recursive case: gcd(a,b) = gcd(b, a%b)
    return gcd(b, a % b);
}

✅ This is one of the oldest known algorithms (~300 BC)! Clean, elegant, no helper function needed. 这是已知最古老的算法之一（约公元前 300 年）！简洁优雅，不需要辅助函数。

🐇 Task 2: Fibonacci (Rabbit Problem) 🐇 任务 2：斐波那契（兔子问题）

The rabbit problem produces the Fibonacci sequence. Each month's rabbit count = previous two months combined. 兔子问题产生斐波那契数列。每月兔子数 = 前两个月之和。

Month月份	Adult Pairs成年兔对	Baby Pairs幼兔对	Total Pairs总对数	rabbits(n)函数返回值
0	0	1	1	2 (=1 pair × 2)
1	1	0	1	2
2	1	1	2	4
3	2	1	3	6
4	3	2	5	10
5	5	3	8	16

⚡ Formula: rabbits(n) = rabbits(n-1) + rabbits(n-2) ⚡ 公式：rabbits(n) = rabbits(n-1) + rabbits(n-2)

Note: function returns number of individual rabbits (pairs × 2), so base cases return 2. 注意：函数返回兔子只数（对数 × 2），所以基础情况返回 2。

Implementation 实现代码

long long rabbits(int months) {
    if (months == 0) return 2;   // 1 pair = 2 rabbits
    if (months == 1) return 2;   // still 1 pair
    return rabbits(months - 1) + rabbits(months - 2);
}

⚠️ Performance Problem!性能问题！

This naive recursion has O(2ⁿ) time complexity. rabbits(60) takes hours because the same values are recalculated millions of times. 这种朴素递归的时间复杂度是 O(2ⁿ)。rabbits(60) 要跑几小时，因为相同的值被重复计算了百万次。

Fix: Memoization (cache results) → O(n) time. 解决方案：记忆化（缓存结果）→ O(n) 时间。

🔗 Recursion with Linked Lists 🔗 链表递归

A linked list is naturally recursive: it's either empty (NULL) or a node followed by a smaller linked list. 链表天然是递归的：它要么是空（NULL），要么是一个节点后跟着更小的链表。

struct node { int value; struct node *next; // pointer to next node (or NULL) }; Visualized: [6] → [8] → [9] → [2] → NULL ↑ last node's next

📋 Linked List Recursion Template: 📋 链表递归模板：

int someFunc(struct node *list) {
    // Base case: empty list or single node
    if (list == NULL) return 0;

    // Recursive case: do something with list->value
    // then recurse on list->next
    return list->value + someFunc(list->next);
}

TASK 3 listTail — Find Last Element listTail — 找最后一个元素

Key insight: The last node has next == NULL. 核心洞察：最后一个节点的 next == NULL。

int listTail(struct node *list) {
    // Base case: this is the last node
    if (list->next == NULL) {
        return list->value;
    }
    // Recursive case: last element is in the rest
    return listTail(list->next);
}

TASK 4 listMax — Find Largest Element listMax — 找最大元素

Key insight: max of list = max(current value, max of rest). 核心洞察：链表最大值 = max(当前值, 剩余链表最大值)。

int listMax(struct node *list) {
    // Base case: only one node
    if (list->next == NULL) {
        return list->value;
    }
    // Recursive case: compare current with max of rest
    int maxOfRest = listMax(list->next);
    if (list->value > maxOfRest) {
        return list->value;
    } else {
        return maxOfRest;
    }
}

TASK 5 ⭐ listShift — Rotate Last Node to Front listShift — 把最后节点移到最前

This is the hardest task. Move the last node to the front without creating new nodes. 这是最难的任务。把最后一个节点移到最前面，不能创建新节点。

Before: [16] → [5] → [2] → NULL After: [2] → [16] → [5] → NULL

💡 Strategy: 3 cases 💡 策略：3 种情况

1 node: return as-is1 个节点：直接返回
2 nodes: manually swap (must cut old link to avoid cycle!)2 个节点：手动交换（必须切断旧链接避免循环！）
3+ nodes: recurse, then insert current node after new head3+ 个节点：递归后，把当前节点插到新头之后

struct node *listShift(struct node *list) {
    // Case 1: single node, nothing to shift
    if (list->next == NULL) {
        return list;
    }

    // Case 2: two nodes — manually swap
    if (list->next->next == NULL) {
        struct node *last = list->next;
        list->next = NULL;    // MUST cut link to avoid cycle!
        last->next = list;
        return last;
    }

    // Case 3: 3+ nodes — recurse on rest, then insert current after newHead
    struct node *newHead = listShift(list->next);
    // list->next still points to the 2nd node (now last in shifted list)
    list->next->next = list;  // append current to end
    list->next = NULL;        // current becomes new tail
    return newHead;
}

⚠️ Why does Case 2 need list->next = NULL? 为什么 Case 2 需要 list->next = NULL？

Without it: [2]→[1]→[2]→[1]→... infinite loop! Cutting the link first prevents the cycle. 不切断的话：[2]→[1]→[2]→[1]→... 无限循环！先切断链接才能防止循环。

📦 Wrapper Struct & Helper Functions 📦 包装结构体与辅助函数

Tasks 6–8 use a wrapper struct that contains the head pointer. Since we recurse on nodes (not the wrapper), we need a helper function. 任务 6–8 使用包含头指针的包装结构体。因为递归是对节点进行的，所以需要辅助函数。

// Two-level structure: struct list { struct node *head; // points to first node }; // To recurse, we use a helper that takes struct node * int listFunc(struct list *list) { return listFuncHelper(list->head); // pass the node pointer } int listFuncHelper(struct node *node) { // recurse here on node->next }

TASK 6 listSum — Sum All Elements listSum — 求所有元素之和

// Helper: recurse on nodes
int listSumHelper(struct node *node) {
    if (node == NULL) return 0;          // empty list → sum is 0
    return node->value + listSumHelper(node->next);
}

// Main function: entry point
int listSum(struct list *list) {
    return listSumHelper(list->head);
}

Note: base case is node == NULL (not node->next == NULL) because the list can be empty (size 0). 注意：基础情况是 node == NULL 而非 node->next == NULL，因为链表可能是空的（size 为 0）。

TASK 7 listInsertOrdered — Insert into Sorted List listInsertOrdered — 插入有序链表

Insert a value while keeping the list sorted. The helper returns the new head of the sublist. 在保持排序的同时插入一个值。辅助函数返回子链表的新头。

struct node *insertHelper(struct node *node, int value) {
    // Base cases: insert here if list is empty OR value fits here
    if (node == NULL || value <= node->value) {
        struct node *new = newNode(value);
        new->next = node;    // works for both NULL and existing node
        return new;
    }
    // Recursive case: value is larger, keep looking
    node->next = insertHelper(node->next, value);
    return node;
}

void listInsertOrdered(struct list *list, int value) {
    list->head = insertHelper(list->head, value);
    // Must update head in case new node is inserted at front
}

TASK 8 listInsertNth — Insert at Position n listInsertNth — 在第 n 个位置插入

Insert at position n (0-indexed). If list is shorter than n, insert at the end. 在第 n 个位置插入（从 0 开始）。如果链表长度不足 n，则插入末尾。

struct node *helper(struct node *node, int n, int value) {
    // Insert here if: position reached OR end of list
    if (n == 0 || node == NULL) {
        struct node *new = newNode(value);
        new->next = node;
        return new;
    }
    // Recursive case: move to next position, decrement n
    node->next = helper(node->next, n - 1, value);
    return node;
}

void listInsertNth(struct list *list, int n, int value) {
    list->head = helper(list->head, n, value);
}

📊 All Tasks Summary 📊 所有任务总结

Task任务	Base Case基础情况	Recursive Case递归情况	Helper?辅助函数？
gcd	`b == 0`	`gcd(b, a%b)`	No否
rabbits	`months == 0 or 1`	`r(n-1) + r(n-2)`	No否
listTail	`next == NULL`	`listTail(next)`	No否
listMax	`next == NULL`	`max(val, listMax(next))`	No否
listShift	1 or 2 nodes1 或 2 个节点	recurse + relink递归 + 重连	No否
listSum	`node == NULL`	`val + sum(next)`	Yes是
listInsertOrdered	`NULL or val ≤ node`	recurse + relink递归 + 重连	Yes是
listInsertNth	`n==0 or NULL`	recurse(n-1) + relink递归(n-1) + 重连	Yes是