COMP2521 Week 2 Recursion Quiz | UNSW Study Materials

Q1 Basic

What are the TWO required components of every recursive function? 每个递归函数都必须有哪两个组成部分？

A A loop and a return statement 一个循环和一个返回语句
B A base case and a recursive case 一个基础情况和一个递归情况
C A helper function and a wrapper function 一个辅助函数和一个包装函数
D A global variable and a local variable 一个全局变量和一个局部变量

✅ B. Every recursive function must have: (1) a base case — when to stop, and (2) a recursive case — calling itself with a smaller problem. Without a base case, you get infinite recursion and a stack overflow crash. 每个递归函数必须有：(1) 基础情况 — 何时停止，(2) 递归情况 — 用更小的问题调用自己。没有基础情况会导致无限递归和栈溢出崩溃。

Q2 Basic

What does gcd(0, 42) return according to Euclid's algorithm? 根据欧几里得算法，gcd(0, 42) 返回什么？

A0
B1
C42
D undefined未定义

✅ C — 42. In our implementation gcd(a, b): when b == 0, return a. Here a=0, b=42 → call gcd(42, 0%42=0) → b==0, return 42. 在我们的实现 gcd(a, b) 中：当 b == 0 时返回 a。这里 a=0, b=42 → 调用 gcd(42, 0%42=0) → b==0，返回 42。

Q3 Basic

What is the base case of gcd(a, b)? gcd(a, b) 的基础情况是什么？

Aa == b
Ba == 0
Cb == 0
Da % b == 0

✅ C. When b == 0, gcd(a, b) returns a. The identity is gcd(a,b) = gcd(b, a%b), so b keeps shrinking until it reaches 0. 当 b == 0 时，gcd(a, b) 返回 a。公式是 gcd(a,b) = gcd(b, a%b)，所以 b 不断缩小直到为 0。

Q4 Basic

Why does rabbits(n) return 2 for both n=0 and n=1? 为什么 rabbits(n) 对 n=0 和 n=1 都返回 2？

A Because there are always 2 pairs of rabbits at the start 因为开始时总有 2 对兔子
B Because we return individual rabbits, not pairs. 1 pair = 2 rabbits 因为返回的是兔子只数而非对数，1 对 = 2 只
C Because the rabbits breed instantly 因为兔子立即繁殖
D It's a coding error, should return 1 这是代码错误，应该返回 1

✅ B. The function counts individual rabbits. At month 0 and month 1, there is exactly 1 pair of rabbits = 2 individual rabbits. The function returns 2 (not 1) because it counts individuals. 该函数统计的是兔子只数。第 0 个月和第 1 个月各有 1 对兔子 = 2 只兔子。函数返回 2（不是 1），因为它统计的是个体数量。

Q5 Intermediate

What is rabbits(4)? rabbits(4) 等于多少？

A6
B8
C10
D12

✅ C — 10. rabbits(4) = rabbits(3) + rabbits(2) = 6 + 4 = 10. Trace: r(0)=2, r(1)=2, r(2)=4, r(3)=6, r(4)=10. rabbits(4) = rabbits(3) + rabbits(2) = 6 + 4 = 10。推导：r(0)=2, r(1)=2, r(2)=4, r(3)=6, r(4)=10。

Q6 Intermediate

Why is naive Fibonacci recursion so slow for large inputs like rabbits(60)? 为什么朴素的斐波那契递归对大输入（如 rabbits(60)）很慢？

A Because long long arithmetic is slow 因为 long long 运算很慢
B Because the same subproblems are computed exponentially many times — O(2ⁿ) 因为相同的子问题被指数级地重复计算 — O(2ⁿ)
C Because recursion itself is inherently slow 因为递归本身就很慢
D Because of the two base cases 因为有两个基础情况

✅ B. The same values are recomputed over and over. For example, rabbits(2) is computed millions of times when computing rabbits(60). This gives O(2ⁿ) complexity. Memoization (caching results) reduces this to O(n). 相同的值被反复计算。例如，计算 rabbits(60) 时，rabbits(2) 被计算了数百万次。这导致 O(2ⁿ) 的复杂度。记忆化（缓存结果）可以将其降低到 O(n)。

Q7 Basic

How do you identify the last node in a linked list? 如何识别链表中的最后一个节点？

A Its value is 0 它的值为 0
B list->next == NULL
C list == NULL
D Its address is the largest 它的内存地址最大

✅ B. The last node's next pointer is NULL. When list->next == NULL, there is no next node — this is the last one. Note: list == NULL means the list itself is empty, not that you've found the last node. 最后一个节点的 next 指针是 NULL。当 list->next == NULL 时，表示没有下一个节点 — 这就是最后一个。注意：list == NULL 表示链表为空，而不是找到了最后一个节点。

Q8 Basic

For listTail([6, 8, 9, 2, 5, 1, 3]), what is returned? listTail([6, 8, 9, 2, 5, 1, 3]) 返回什么？

A6
B1
C3
D9

✅ C — 3. listTail returns the value of the last node. The last element in [6, 8, 9, 2, 5, 1, 3] is 3. listTail 返回最后一个节点的值。[6, 8, 9, 2, 5, 1, 3] 的最后一个元素是 3。

Q9 Basic

For listMax([7, 2, 6, 8, 0]), what is returned? listMax([7, 2, 6, 8, 0]) 返回什么？

A0
B7
C6
D8

✅ D — 8. listMax recursively compares each value with the max of the rest. The largest value in [7, 2, 6, 8, 0] is 8. listMax 递归地将每个值与剩余部分的最大值进行比较。[7, 2, 6, 8, 0] 中的最大值是 8。

Q10 Intermediate

What does the following code return for list [5] (single element)? 以下代码对链表 [5]（单个元素）返回什么？

int listMax(struct node *list) {
    if (list->next == NULL) return list->value;
    int maxOfRest = listMax(list->next);
    return (list->value > maxOfRest) ? list->value : maxOfRest;
}

A 0 (default)0（默认值）
B5
CNULL
D Crashes崩溃

✅ B — 5. For a single node, list->next == NULL is true, so we immediately return list->value which is 5. The base case handles single-element lists correctly. 对于单个节点，list->next == NULL 为真，所以直接返回 list->value 即 5。基础情况正确处理了单元素链表。

Q11 Intermediate

What does listShift([16, 5, 2]) produce? listShift([16, 5, 2]) 的结果是什么？

A[5, 2, 16]
B[2, 16, 5]
C[16, 2, 5]
D[2, 5, 16]

✅ B — [2, 16, 5]. listShift moves the last node to the front. The last node (2) becomes the new head, and the rest maintain their relative order: [2, 16, 5]. listShift 将最后一个节点移到最前面。最后一个节点（2）成为新头，其余节点保持相对顺序：[2, 16, 5]。

Q12 Advanced

In listShift, why does the 2-node case need list->next = NULL before last->next = list? 在 listShift 中，为什么 2 节点情况在 last->next = list 之前需要 list->next = NULL？

A To free memory 为了释放内存
B To prevent an infinite cycle (last→first→last→...) 防止无限循环（last→first→last→...）
C To satisfy the compiler 为了满足编译器要求
D To make the first node the new head 让第一个节点成为新头

✅ B. For [A, B]: if we skip A->next = NULL, after B->next = A we get B→A→B→A→... an infinite cycle! Setting A->next = NULL first breaks the old link, making A the proper tail. 对于 [A, B]：如果跳过 A->next = NULL，在 B->next = A 之后会得到 B→A→B→A→... 无限循环！先设置 A->next = NULL 断开旧链接，使 A 成为正确的尾节点。

Q13 Basic

Why do Tasks 6–8 need a helper function, but Tasks 3–5 don't? 为什么任务 6–8 需要辅助函数，而任务 3–5 不需要？

A Tasks 6–8 are harder 任务 6–8 更难
B Tasks 6–8 take a struct list * (wrapper), but recursion needs to walk struct node * 任务 6–8 接收 struct list *（包装器），但递归需要遍历 struct node *
C Helper functions make code look professional 辅助函数让代码看起来更专业
D Tasks 6–8 use loops internally 任务 6–8 内部使用了循环

✅ B. Tasks 6–8 accept struct list * (a wrapper with a head pointer). We can't recurse directly on this. A helper function takes struct node * so we can walk the list node-by-node recursively. 任务 6–8 接收 struct list *（带有头指针的包装器）。我们无法直接对此递归。辅助函数接收 struct node *，这样我们就可以逐节点递归地遍历链表。

Q14 Basic

What does listSum([]) (empty list, size=0) return? listSum([])（空链表，size=0）返回什么？

A Crashes with NULL pointer error 崩溃，NULL 指针错误
B-1
C0
D undefined behaviour未定义行为

✅ C — 0. The base case if (node == NULL) return 0 handles empty lists. list->head is NULL for an empty list, so listSumHelper(NULL) returns 0 immediately. The sum of nothing is 0. 基础情况 if (node == NULL) return 0 处理了空链表。空链表的 list->head 为 NULL，所以 listSumHelper(NULL) 立即返回 0。空集合的和为 0。

Q15 Intermediate

In listInsertOrdered, what condition triggers inserting the new node? 在 listInsertOrdered 中，什么条件触发插入新节点？

if (node == NULL || value <= node->value) {
    struct node *new = newNode(value);
    new->next = node;
    return new;
}

A When we reach the end of the list, OR when current node's value is greater/equal 到达链表末尾，或者当前节点的值大于等于要插入的值
B Only when we reach NULL 只有到达 NULL 时
C Only when value is smaller than current 只有当值小于当前节点时
D When the list has more than 2 elements 当链表有超过 2 个元素时

✅ A. Two cases trigger insertion: (1) node == NULL — we've reached the end, insert here as the last node. (2) value <= node->value — the current node is larger/equal, so insert before it to maintain order. 两种情况触发插入：(1) node == NULL — 到达末尾，插入为最后一个节点。(2) value <= node->value — 当前节点更大/相等，在它之前插入以维持顺序。

Q16 Basic

After listInsertOrdered([2, 5, 7], 3), what is the result? listInsertOrdered([2, 5, 7], 3) 后结果是什么？

A[2, 5, 7, 3]
B[3, 2, 5, 7]
C[2, 3, 5, 7]
D[2, 5, 3, 7]

✅ C — [2, 3, 5, 7]. 3 is larger than 2, so we skip 2. 3 is smaller than 5, so insert before 5. Result: [2, 3, 5, 7] — still sorted! 3 大于 2，跳过 2。3 小于 5，所以插入在 5 之前。结果：[2, 3, 5, 7] — 仍然有序！

Q17 Basic

Why must listInsertOrdered do list->head = insertHelper(list->head, value) instead of just calling the helper? 为什么 listInsertOrdered 必须写 list->head = insertHelper(list->head, value) 而不是仅仅调用 helper？

A Because the helper returns NULL 因为 helper 返回 NULL
B Because if the new value is inserted at the front, the head changes and must be updated 因为如果新值插在最前面，头节点会改变，必须更新
C To avoid a memory leak 为了避免内存泄漏
D The helper is not recursive helper 不是递归的

✅ B. If value is smaller than all existing values (e.g. inserting 1 into [2,5,7]), the new node becomes the head. list->head must be updated to point to the new front node. The helper returns the new head each time. 如果值小于所有现有值（例如向 [2,5,7] 插入 1），新节点成为头节点。list->head 必须更新以指向新的头节点。helper 每次返回新的头节点。

Q18 Intermediate

After listInsertNth([16, 7, 8], n=1, value=12), what is the result? listInsertNth([16, 7, 8], n=1, value=12) 后结果是什么？

A[12, 16, 7, 8]
B[16, 12, 7, 8]
C[16, 7, 12, 8]
D[16, 7, 8, 12]

✅ B — [16, 12, 7, 8]. Position 1 means before the element currently at index 1 (which is 7). So 12 is inserted between 16 and 7: [16, 12, 7, 8]. 位置 1 表示在当前索引 1 处的元素（即 7）之前。所以 12 插入在 16 和 7 之间：[16, 12, 7, 8]。

Q19 Intermediate

After listInsertNth([16, 7, 8], n=10, value=12), what is the result? (n is beyond the list length) listInsertNth([16, 7, 8], n=10, value=12) 后结果是什么？（n 超过链表长度）

A Error / crash错误 / 崩溃
B[12, 16, 7, 8]
C[16, 7, 8, 12]
D The list is unchanged链表不变

✅ C — [16, 7, 8, 12]. When node == NULL is reached before n reaches 0, we insert at the end. So listInsertNth with n beyond list length appends to the end. 当 n 尚未到达 0 就遇到 node == NULL 时，我们插入到末尾。所以 n 超过链表长度时，listInsertNth 会追加到末尾。

Q20 Intermediate

In listInsertNth, why does the recursive call pass n - 1 instead of n? 在 listInsertNth 中，为什么递归调用传 n - 1 而不是 n？

A To avoid an off-by-one error 为了避免差一错误
B Each step forward means one position closer to target — we count down to 0 每向前一步，表示距目标位置近了一步 — 我们倒计数到 0
C Because n is always even 因为 n 总是偶数
D So we don't overflow the stack 防止栈溢出

✅ B. We start at position n, and each time we move to the next node, we're one step closer to position 0. When n reaches 0, we're at the target position and insert there. n-1 decrements the counter each recursive step. 我们从位置 n 开始，每次移到下一个节点，就距目标位置 0 近了一步。当 n 达到 0 时，我们到达了目标位置并在那里插入。n-1 在每次递归中递减计数器。

Q21 Basic

What happens if you forget the base case in a recursive function? 如果忘记了递归函数中的基础情况会发生什么？

A The function returns 0 函数返回 0
B The compiler catches the error 编译器捕获错误
C Infinite recursion leading to a stack overflow crash 无限递归导致栈溢出崩溃
D The function runs very slowly but eventually finishes 函数运行非常慢但最终会结束

✅ C. Without a base case, the function keeps calling itself forever. Each call uses stack space. Eventually the stack runs out of memory → segmentation fault / stack overflow. 没有基础情况，函数会一直调用自己。每次调用都使用栈空间。最终栈内存耗尽 → 段错误 / 栈溢出。

Q22 Basic

Which data type should rabbits() return, and why? rabbits() 应该返回什么数据类型，为什么？

A int — always sufficient总是够用
B long long — values can exceed ~2 billion (int max)值可超过约 20 亿（int 最大值）
C float — for large numbers用于大数字
D double — most precise最精确

✅ B — long long. rabbits(42) ≈ 866 million and rabbits(60) ≈ 5 trillion. An int can only store ~2.1 billion. long long (8 bytes) can store up to ~9.2 × 10¹⁸. rabbits(42) ≈ 8.66 亿，rabbits(60) ≈ 5 万亿。int 只能存约 21 亿。long long（8 字节）可存到约 9.2 × 10¹⁸。

Q23 Advanced

In the correct listShift for 3+ nodes, after recursing, why does list->next->next = list correctly append the current node? 在 3+ 节点的正确 listShift 中，递归后为什么 list->next->next = list 能正确追加当前节点？

A Because list->next was updated by the recursion to point to the new tail 因为递归已经将 list->next 更新为指向新的尾节点
B Because list->next still points to the original second node, which is now the tail of the shifted sublist 因为 list->next 仍指向原来的第二个节点，该节点现在是移位后子链表的尾节点
C Because the recursion sets list->next to NULL 因为递归将 list->next 设置为 NULL
D It doesn't work — this causes a cycle 这不对 — 会造成循环

✅ B. After the recursive call, list->next still holds the address of the original 2nd node. In the shifted sublist, that 2nd node is now the tail (its next was set to NULL during the 2-node base case). So list->next->next = list correctly links the current node as the new tail. 递归调用后，list->next 仍保存着原来第 2 个节点的地址。在移位后的子链表中，那个第 2 个节点现在是尾节点（在 2 节点基础情况中它的 next 被设为 NULL）。所以 list->next->next = list 正确地将当前节点链接为新的尾节点。

Q24 Intermediate

What is wrong with this listSum helper? 这个 listSum helper 有什么问题？

int helper(struct node *node) {
    return node->value + helper(node->next);
}

A It uses the wrong variable name 变量名不对
B It's missing the base case — will crash when it hits NULL 缺少基础情况 — 遇到 NULL 时会崩溃
C It should use a loop instead 应该用循环代替
D It adds values in the wrong order 加法顺序不对

✅ B. No base case! When node->next is NULL, the next recursive call tries to access NULL->value → crash (segmentation fault). Must add: if (node == NULL) return 0; 没有基础情况！当 node->next 为 NULL 时，下一次递归调用会尝试访问 NULL->value → 崩溃（段错误）。必须添加：if (node == NULL) return 0;

Q25 Advanced

What technique reduces Fibonacci recursion from O(2ⁿ) to O(n) time? 什么技术能将斐波那契递归的时间从 O(2ⁿ) 降低到 O(n)？

A Using a faster computer 使用更快的计算机
B Memoization — caching already-computed results in an array 记忆化 — 将已计算的结果缓存在数组中
C Using long long instead of int 使用 long long 代替 int
D Adding more base cases 添加更多基础情况

✅ B — Memoization. Store each result in a memo[] array. Before computing f(n), check if it's already cached. If yes, return immediately. Each value is computed only once, reducing complexity from O(2ⁿ) to O(n). 将每个结果存储在 memo[] 数组中。计算 f(n) 之前，先检查是否已缓存。如果是，立即返回。每个值只计算一次，将复杂度从 O(2ⁿ) 降低到 O(n)。