Haskell/解決方案/遞迴

階乘函式

練習

將階乘函式輸入 Haskell 原始檔，並將其載入到 GHCi 中。
嘗試 factorial 5 和 factorial 1000 之類的示例。
- factorial (-1) 怎麼樣？為什麼會這樣？
一個數字 n 的雙階乘是 1（或 2）到 n 之間的隔一個數字的乘積。例如，8 的雙階乘是 8 × 6 × 4 × 2 = 384，而 7 的雙階乘是 7 × 5 × 3 × 1 = 105。在 Haskell 中定義 doubleFactorial 函式。

factorial 可以定義如下

factorial 0 = 1
factorial n = n * factorial(n - 1)

輸入 factorial (-1) 應該會顯示訊息 *** Exception: stack overflow。這是因為根據定義，factorial (-1) 是 (-1) * factorial (-2)，即 (-1) * (-2) * factorial (-3)。這將永遠不會停止，因此函式將一直執行，直到它耗盡記憶體。
doubleFactorial 可以定義如下

doubleFactorial 0 = 1
doubleFactorial 1 = 1
doubleFactorial n = n * doubleFactorial (n-2)

其他遞迴函式

練習

類似於我們上面對 factorial 3 的展開，展開乘法 5 × 4。
定義一個遞迴函式 power，使得 power x y 將 x 提高到 y 次方。
給定一個函式 plusOne x = x + 1。不使用任何其他 (+)，定義一個遞迴函式 addition，使得 addition x y 將 x 和 y 加在一起。
（更難）實現函式 log2，它計算其引數的整數對數（以 2 為底）。也就是說，log2 計算小於或等於其引數的 2 的最大次冪的指數。例如，log2 16 = 4，log2 11 = 3，以及 log2 1 = 0。（小提示：閱讀緊接這些練習的段落的最後一句話。）

1. 5 × 4

4 不等於 1，因此我們遞迴：計算 5 × 3

3 不等於 1，因此我們遞迴

2 不等於 1，因此我們遞迴

1 等於 1，因此我們返回 5

我們將當前數字 5 加到遞迴結果 5 中。我們得到 10

我們將當前數字 5 加到遞迴結果 10 中。我們得到 15

我們將當前數字 5 加到遞迴結果 15 中。我們得到 20。

2.

power x 0 = 1
power x y = x * power x (y-1)

3.

addition x 0 = x
addition x y = plusOne (addition x (y-1))

4.

log2 1 = 0
log2 n = 1 + log2 (n `div` 2) -- the "`" make div into infix notation

基於列表的遞迴

練習

為以下基於列表的函式給出遞迴定義。在每種情況下，考慮基本情況是什麼，然後考慮一般情況在比它小的所有事物方面會是什麼樣子。

replicate :: Int -> a -> [a]，它接受一個元素和一個計數，並返回一個列表，其中該元素重複了該次數。例如，replicat 3 'a' = "aaa"。（提示：考慮任何計數為 0 的內容的副本應該是多少；計數為 0 是你的“基本情況”。）
(!!) :: [a] -> Int -> a，它返回給定“索引”處的元素。第一個元素位於索引 0 處，第二個元素位於索引 1 處，依此類推。注意，使用此函式，你正在以數字和列表方式進行遞迴。
（有點難。）zip :: [a] -> [b] -> [(a, b)]，它接受兩個列表並將它們“壓縮”在一起，使得結果列表中的第一對是兩個列表的第一個兩個元素，依此類推。例如，zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]。如果任一列表比另一個短，則可以在任一列表耗盡後停止。例如，zip [1,2] "abc" = [(1, 'a'), (2, 'b')]。
使用輔助函式和累積引數定義 length，如 factorial 的迴圈式替代版本。

1-3 的答案，在一個程式碼塊中

replicat 0 _     = []
replicat n thing = thing : replicat (n-1) thing

[]     !! _ = error "Index too large" -- An empty list has no elements.
(x:_)  !! 0 = x
(x:xs) !! n = xs !! (n-1)

zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

(x:xs) 不匹配空列表，因此你也可以有

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _      _      = []

以下是累積的 length

length xs = go 0 xs
    where
    go acc []     = acc
    go acc (_:xs) = go (acc + 1) xs