遞迴技術的典型範例之一，是 Hoare 在 1962 年提出的所謂 Quick Sort 演算法。 他的基本想法如下。
如果 v 是一個序列，我們要將 v 內的元素從小到大依序排好。 可以這樣想：從 v 內任挑一個元素，稱它為「標竿」 (pole)， 將 v 中所有小於標竿的元素全部挪到它的左邊， 所有不小於 (>=) 標竿的元素都挪到它的右邊。 這樣挪移之後，標竿左邊的元素都比它小、標竿右邊的元素都不比它小。 那麼，如果分別把左邊和右邊的元素都排好順序，整個 v 就完成排序了。 而左邊的元素、右邊的元素，不又是兩個序列嗎？ 何不再用同樣的想法去對付他們。 這就是遞迴想法了。
如果寫了一個函式 qsort() 來實現 Quick Sort 演算法， 就是把 v 分成小於 pole 的序列 u 和不小於 pole 的序列 w， 然後
[qsort(u), pole, qsort(w)]就是完成排序的答案。
使用遞迴，就像 while 迴圈一樣，得要想一個問題：它如何停止？ 總不能無止境地遞迴下去，那可得不到答案。 以上述的 qsort() 想法為例，顯然 u 和 w 的元素個數至少比 v 少一個 (少了 pole)。因此，每遞迴一層，當作參數的序列元素就少一個 (以上)。 總有一天那序列的元素個數會是一個或零個 (空序列)。 在這個情況下，根本不必排序，只要把傳過來的序列 (只有一個元素、或沒有元素) 再傳回去就好了。這就是 qsort() 的停止方式。
以下就是用 Matlab 來實現 qsort() 的一種寫法。
function sorted = qsort(v)
n = length(v); % n 是 v 的元素個數
if (n > 1)
u = []; % 如果 n > 1 則將 v 分成 u 和 w 兩段
w = []; % 將 u 和 w 準備好，一開始它們是空序列
pole = v(1); % pole 即標竿，我們選 v(1) 擔任標竿
for k = 2:n % 把 v 的其他元素一一和標竿比小
if (v(k) < pole)
u = [u, v(k)]; % 比標竿小的元素放到 u 序列裡面
else
w = [w, v(k)]; % 其他元素放到 w 序列裡面
end
end
sorted = [qsort(u), pole, qsort(w)];
else
sorted = v;
end % 函式結束，把 sorted 序列傳回上層呼叫者如果
x = [2 0 7 4 9 5];則
qsort(x)的排序結果 (當然和 sort(x) 一樣)，是 [0 2 4 5 7 9]。 讓我們來看看 Matlab 實際上依照 qsort() 程式做了什麼？
當 Matlab 呼叫 qsort(x)，開始了第一層的 qsort()， 它得到
v = [2 0 7 4 9 5]此時 pole 是 2 而
u = [0] 和 w = [7 4 9 5]第一層呼叫 qsort(u)，這就開始了第二層的第一次。
第二層第一次的 qsort() 函式得到
v = [0]因為只有一個元素，所以傳回 sorted=[0] 給第一層。 第二層第一次結束，回到第一層。
第一層得到 qsort(u) 的答案 [0]， 接著呼叫 qsort(w)，這就開始了第二層的第二次。
第二層第二次的 qsort() 函式得到
v = [7 4 9 5]此時 pole 是 7 而
u = [4 5] 和 w = [9]第二層第二次呼叫 qsort(u)，這就開始了第三層的第一次。
第三層第一次的 qsort() 函式得到
v = [4 5]此時 pole 是 4 而
u = [] 和 w = [5]第三層第一次呼叫 qsort(u)，這就開始了第四層的第一次。
第四層第一次的 qsort() 函式得到
v = []是一個空序列，所以傳回 sorted=[] 給呼叫它的第三層第一次。 第四層第一次結束，回到第三層第一次。
第三層第一次的 qsort(u) 得到答案 []， 接著它呼叫 qsort(w)，這就開始了第四層的第二次。
第四層第二次的 qsort() 函式得到
v = [5]只有一個元素，所以傳回 sorted=[5] 給呼叫它的第三層第一次。 第四層第二次結束，回到第三層第一次。
第三層第一次的 qsort(w) 得到答案 [5]， 因此它的 sorted=[[],4,[5]]=[4,5] 做出答案了， 傳回給呼叫它的第二層第二次。 第三層第一次結束，回到第二層第二次。
第二層第二次的 qsort(u) 得到答案 [4,5]， 接著它呼叫 qsort(w)，這就開始了第三層的第二次。
第三層第二次的 qsort() 函式得到
v = [9]只有一個元素，所以傳回 sorted=[9] 給呼叫它的第二層第二次。 第三層第二次結束，回到第二層第二次。
第二層第二次的 qsort(w) 得到答案 [9]， 因此它的 sorted=[[4,5],7,[9]]=[4,5,7,9] 做出答案了， 傳回給呼叫它的第一層。 第二層第二次結束，回到第一層。
第一層 qsort(w) 得到答案 [4,5,7,9]， 因此它的 sorted=[[0],2,[4,5,7,9]]=[0,2,4,5,7,9] 做出答案了， 傳回給呼叫它的 Matlab 介面。 至此，整個 qsort(x) 結束，得到答案 [0 2 4 5 7 9]。
前面的敘述有點亂，讀者不妨試著按照文字敘述畫一張樹狀圖表出來， 比較容易看清楚整個流程。
習題