← 回首頁

遞迴家族(河內塔 / 最大子陣列 / N 皇后)

碰到一個大問題,如果它能拆成「形狀一樣、只是小一號」的問題,那就可以丟給「縮小版的自己」去解——這就是遞迴,像俄羅斯娃娃一層套一層,拆到最小那顆能直接回答,再一路往回把答案組起來。這頁用三個經典題示範遞迴的三種常見長相:河內塔只管把問題拆小、最大子陣列拆完還得把兩半的結果合併、N 皇后走不通就退回上一步換個走法重試。下面你可以一步步看它們怎麼往下拆、又怎麼往回收。

三個經典問題示範遞迴的三種典型用法:

1. 河內塔(Tower of Hanoi,n=3)

將 n 個盤子從來源柱 A 移到目標柱 C,可借助輔助柱 B:先遞迴把上方 n-1 個盤子從 A 移到 B(借助 C), 再把第 n 個(最大)盤直接從 A 移到 C,最後遞迴把 n-1 個盤子從 B 移到 C(借助 A)。n=1 時直接移動,不再遞迴。

固定示範:n=3(3 個盤子,A→C,借助 B),共 7 步
移動次數:0 目前移動:
每柱由下而上堆疊盤子,盤寬與編號成正比(愈大盤愈寬);紅框標示剛移入的盤。

呼叫棧(depth=0

移動紀錄

2. 最大子陣列和(Maximum Subarray,分治法)

將陣列一分為二,答案要嘛完全落在左半、要嘛完全落在右半、要嘛跨越中點;跨中情形需從中點分別向左、向右各自累加取最大值再相加。 區段長度為 1 時直接回傳該元素(base case)。

固定示範(同 max-subarray.test.js MAXSUB_ARR):[-2, 1, -3, 4, -1, 2, 1, -5, 4](CLRS 範例,答案 6,來自 [4,-1,2,1])
比較次數:0
藍色外框(active)為目前處理的區段;粉紅(pivot)標示中點 mid,用於跨中掃描。

目前最大和 bestSum

分治呼叫棧(segments,range/phase/result)

3. N 皇后(N-Queens,回溯法,n=4)

逐列嘗試每一欄放皇后:若與已放置的皇后同欄或同對角線衝突,立即剪枝、跳過此欄,不再往下遞迴; 安全則放置並遞迴下一列,回溯時移除該皇后再嘗試下一欄。放滿 n 列即為一組解。

固定示範:n=4(4×4 棋盤),共 2 組解
嘗試放置次數:0
藍色外框(active)為目前嘗試放置的格子;粉紅(pivot)標示與之衝突的既有皇后。

每列皇后(row → col,未放為 -;目前處理列標色)

已找到解(共 0 組