[Rust] 單元測試與效能基準測試 (benchmark) ：以某遞迴問題為例

這是在 PTT C/C++ 板上面看到的問題 (https://www.ptt.cc/bbs/C_and_CPP/M.1498011747.A.BC3.html)，摘錄問題描述如下：

輸入       得到
(n) -> 1 (n-1)(n-1)

例如
(0) -> 0
(1) -> 100
(2) -> 1100100
(3) -> 111001001100100

或者把定義的部份寫成

f(0) = "0"
f(n) = "1" ++ f(n-1) ++ f(n-1)

（假設 ++ 是字串接合運算符號）

自問題描述可以看出這是遞迴定義。怎麼說？因為第 n 個結果是利用第 n - 1 個結果組合而成。

這樣的問題可以用直覺遞迴來解，也可以寫成迴圈來解，也可以用動態規劃來解。

在實作完上述的演算法後，可以利用自動測試來測試演算法的實作是否沒問題。而為了比較這些實作之間在各種場合下的優劣，可以利用效能基準測試（benchmark）來互相比較。

非常幸運的是，Rust 的基本開發工具裡面已經包含了這些工具。單元測試的部份，可以在第二版的 Rust 程式書找到：https://doc.rust-lang.org/book/second-edition/ch11-00-testing.html 。至於只在 nightly 才有的效能基準測試，則在第一版的書裡面 https://doc.rust-lang.org/1.4.0/book/benchmark-tests.html 。

千秋所做的程式碼在 https://gitlab.com/chiakikame/rust-recurse-algorithm-fun 可以找到。因為千秋也在學習中，歡迎諸位大德不吝指教以及討論。