如果你的孩子能夠走迷宮——嘗試每一個岔路，在死路盡頭悄悄退回——那麼他其實已經領會了競賽程式設計中兩個最重要思想的直覺：遞迴與回溯。
遞迴是指透過讓函式在同一問題的更小版本上呼叫自身來求解問題的方法。回溯在此基礎上系統地探索解空間，一旦某個部分答案不可能導向有效結果，就立即將其捨棄。兩者共同支撐了學生在美國計算機奧林匹亞（USA Computing Olympiad）等競賽中遇到的大量題目。本指南將解釋它們是什麼、會在哪裡出現，以及如何高效地練習它們。
遞迴與回溯到底做了什麼
遞迴把一個大任務拆分為更小的、自相似的子任務。每個遞迴函式都需要兩個部分：終止呼叫的基線情形（base case），以及朝著該基線情形推進的遞迴情形（recursive case）。經典的入門範例包括計算階乘、走訪樹，或產生一個集合的所有子集。
回溯是應用於搜尋的遞迴。演算法從一個空的候選解開始，每次擴充一個選擇。做出選擇後遞迴下去；如果該分支失敗或已被完全探索，就撤銷該選擇並嘗試下一個選項。這種「選擇、探索、撤銷選擇」的節奏，本質上就是在一棵可能性之樹上進行深度優先搜尋。
一個簡單的心智模型：遞迴是你如何深入下去，而回溯是你在走到死路後如何退回上一層，從而不遺漏任何一種可能。
回溯能夠乾淨俐落解決的問題
- 產生組合：一個集合的所有子集、排列或排布方式。
- 約束類謎題：N 皇后問題、數獨和圖著色。
- 路徑計數：統計在某些格子可能被阻擋的網格中穿行的路線數。
- 文字與拼塊遊戲：拼出有效單字，或將拼塊放入棋盤。
這些技巧在競賽中出現在何處
在 USACO 中，參賽者被分入難度遞增的四個組別——Bronze、Silver、Gold 和 Platinum。新參賽者從 Bronze 開始，成績優異者可晉級至下一級別。根據 USACO Guide，完全搜尋（complete-search）遞迴早在 Bronze 組就已出現，而遞迴搜尋與回溯則在 Silver 級別作為深度優先搜尋的一部分被正式引入。競賽通常在一個固定視窗內連續進行數小時，而具體日期、規則和晉級門檻每個賽季都會變化，因此請務必在 USACO 官方網站上確認最新資訊。
除了 USACO，這些技能還可以直接遷移到其他奧賽風格的評測系統以及更廣泛的演算法面試中。這正是為什麼這些模式構成了任何一套嚴肅的競賽程式設計課程的核心。
如何高效練習
回溯雖然強大，但可能很慢：在最壞情況下，搜尋樹會呈指數級增長。區分強手的關鍵技能在於剪枝——盡可能早地砍掉不可能成功的分支。有效的練習聚焦於三個習慣：
- 反覆書寫範本，直到形成本能。選擇一個候選，檢查它是否有效，遞迴，然後撤銷該選擇。在嘗試更難的題目之前，先在子集和排列上反覆操練。
- 有意識地加入剪枝。在每一步都問自己：「這個部分解還有可能成立嗎？」越早檢查越嚴格的約束，就能消除越龐大的子樹。例如在 N 皇后問題中，拒絕把兩個皇后放在同一行（同一列）或同一對角線上，幾乎可以瞬間剪掉大部分搜尋。
- 估算搜尋規模。在編寫程式之前，先勾勒出存在多少候選。如果即便剪枝之後數量仍然大到天文數字，那麼預期的解法很可能是動態規劃或貪婪方法，而非回溯。
遞迴教會學生信任自己解法的更小版本。回溯教會他們大膽地探索、誠實地退回。兩者都是嚴謹思維的習慣，而不只是程式設計技巧。
這些基礎也與相鄰領域相通。同樣的遞迴搜尋結構支撐著人工智慧中的賽局樹探索，以及機器人自主行為背後的規劃邏輯——這就是為什麼掌握了回溯的學生往往能在各個 STEM 學科中快速進步。
開始培養這項技能
遞迴與回溯所回報的，是穩定、有結構的練習，而遠非天賦。藉助清晰的範本、聰明的剪枝以及合適的題目階梯，有動力的學生可以在一個賽季內從困惑走向自信。
在 BIAA，我們的教練會引導學生走過的正是這條進階之路——從第一個遞迴函式，到可以應對競賽的搜尋能力。歡迎了解我們的競賽程式設計課程，看看我們如何幫助 K-12 學生備戰 USACO 乃至更高的目標。