F# 程式設計/遞迴
| F# : 遞迴和遞迴函式 |
遞迴函式是指呼叫自身的函式。有趣的是，與許多其他語言不同，F# 中的函式預設情況下不是遞迴的。程式設計師需要使用rec關鍵字顯式地將函式標記為遞迴。
let rec someFunction = ...
非負整數 n 的階乘，用 n! 表示，是所有小於或等於 n 的正整數的乘積。例如，6! = 6 * 5 * 4 * 3 * 2 * 1 = 720。
在數學中，階乘定義如下
自然地，我們會用手計算階乘，如下所示
fact(6) =
= 6 * fact(6 - 1)
= 6 * 5 * fact(5 - 1)
= 6 * 5 * 4 * fact(4 - 1)
= 6 * 5 * 4 * 3 * fact(3 - 1)
= 6 * 5 * 4 * 3 * 2 * fact(2 - 1)
= 6 * 5 * 4 * 3 * 2 * 1 * fact(1 - 1)
= 6 * 5 * 4 * 3 * 2 * 1 * 1
= 720
在 F# 中，階乘函式可以簡明地編寫如下
let rec fact x =
if x < 1 then 1
else x * fact (x - 1)
但請注意，此函式按原樣返回所有負數的 1，但階乘對於負數是未定義的。這意味著在實際的生產程式中，您必須要麼設計程式的其餘部分，使其永遠不會使用負數呼叫階乘，要麼捕獲負輸入並丟擲異常。異常將在後面的章節中討論。
這是一個完整的程式
open System
let rec fact x =
if x < 1 then 1
else x * fact (x - 1)
(* // can also be written using pattern matching syntax:
let rec fact = function
| n when n < 1 -> 1
| n -> n * fact (n - 1) *)
Console.WriteLine(fact 6)
最大公約數或 GCD 函式計算能整除另外兩個整數的最大整數。例如，能整除 259 和 111 的最大數是 37，記為 GCD(259, 111) = 37。
歐幾里得發現了一種非常簡單的遞迴演算法來計算兩個數的 GCD
為了用手計算，我們會寫
gcd(259, 111) = gcd(111, 259% 111)
= gcd(111, 37)
= gcd(37, 111% 37)
= gcd(37, 0)
= 37
在 F# 中，我們可以使用%（模數）運算子來計算兩個數的餘數，因此我們自然可以將 F# 中的 GCD 函式定義如下
open System
let rec gcd x y =
if y = 0 then x
else gcd y (x % y)
Console.WriteLine(gcd 259 111) // prints 37
假設我們有一個函式A，它在某個時刻呼叫函式B。當B執行完畢時，CPU 必須從中斷的地方繼續執行A。為了“記住”返回的位置，函式A將一個返回地址作為額外的引數傳遞給堆疊上的B；B在執行完畢後跳轉到返回地址。這意味著呼叫函式，即使是沒有任何引數的函式，也會消耗堆疊空間，並且遞迴函式很容易消耗堆疊上的所有可用記憶體。
一個尾遞迴函式是遞迴的一種特殊情況，其中方法中執行的最後一條指令是遞迴呼叫。F# 和許多其他函式式語言可以最佳化尾遞迴函式；由於遞迴呼叫後沒有執行額外的操作，因此函式不需要記住它來自哪裡，因此沒有理由在堆疊上分配額外的記憶體。
F# 透過告訴 CLR 在執行目標函式之前放棄當前堆疊幀來最佳化尾遞迴函式。因此，尾遞迴函式可以無限遞迴，而不會消耗堆疊空間。
這是一個非尾遞迴函式
> let rec count n =
if n = 1000000 then
printfn "done"
else
if n % 1000 = 0 then
printfn "n: %i" n
count (n + 1) (* recursive call *)
() (* <-- This function is not tail recursive
because it performs extra work (by
returning unit) after
the recursive call is invoked. *);;
val count : int -> unit
> count 0;;
n: 0
n: 1000
n: 2000
n: 3000
...
n: 58000
n: 59000
Session termination detected. Press Enter to restart.
Process is terminated due to StackOverflowException.
讓我們看看如果我們使函式正確地尾遞迴會發生什麼
> let rec count n =
if n = 1000000 then
printfn "done"
else
if n % 1000 = 0 then
printfn "n: %i" n
count (n + 1) (* recursive call *);;
val count : int -> unit
> count 0;;
n: 0
n: 1000
n: 2000
n: 3000
n: 4000
...
n: 995000
n: 996000
n: 997000
n: 998000
n: 999000
done
如果沒有對n = 1000000進行檢查，函式將無限執行。確保所有遞迴函式都有一個基本情況以確保它們最終終止非常重要。
假設為了娛樂，我們想根據更基本的加法函式來實現乘法函式。例如，我們知道6 * 4與6 + 6 + 6 + 6相同，或者更一般地，我們可以遞迴地定義乘法為M(a, b) = a + M(a, b - 1), b > 1。在 F# 中，我們將這樣編寫這個函式
let rec slowMultiply a b =
if b > 1 then
a + slowMultiply a (b - 1)
else
a
可能並不立即顯而易見，但此函式不是尾遞迴的。如果我們將函式改寫如下，可能更加明顯
let rec slowMultiply a b =
if b > 1 then
let intermediate = slowMultiply a (b - 1) (* recursion *)
let result = a + intermediate (* <-- additional operations *)
result
else a
它不是尾遞迴的原因是在遞迴呼叫slowMultiply之後，必須將遞迴的結果加到a。請記住，尾遞迴需要最後一步是遞迴。
由於slowMultiply函式不是尾遞迴的，因此對於導致非常深層遞迴的輸入，它會丟擲StackOverFlowException
> let rec slowMultiply a b =
if b > 1 then
a + slowMultiply a (b - 1)
else
a;;
val slowMultiply : int -> int -> int
> slowMultiply 3 9;;
val it : int = 27
> slowMultiply 2 14;;
val it : int = 28
> slowMultiply 1 100000;;
Process is terminated due to StackOverflowException.
Session termination detected. Press Enter to restart.
可以使用累加引數將大多數遞迴函式重寫為尾遞迴形式
> let slowMultiply a b =
let rec loop acc counter =
if counter > 1 then
loop (acc + a) (counter - 1) (* tail recursive *)
else
acc
loop a b;;
val slowMultiply : int -> int -> int
> slowMultiply 3 9;;
val it : int = 27
> slowMultiply 2 14;;
val it : int = 28
> slowMultiply 1 100000;;
val it : int = 100000
內部迴圈中的累加器引數在每次遞迴迭代中儲存函式的狀態。
解決方案.
以下函式計算斐波那契數列中的第n個數字
let rec fib = function
| n when n=0I -> 0I
| n when n=1I -> 1I
| n -> fib(n - 1I) + fib(n - 2I)
- 注意: 上述函式的型別為
val fib : bigint -> bigint。之前我們一直在使用int或System.Int32型別來表示數字，但這種型別最大值為2,147,483,647。型別bigint用於任意大小整數，例如具有數十億位數的整數。bigint的最大值僅受使用者機器上可用記憶體的限制，但對於大多數實際的計算目的，我們可以說此型別是無界的。
上述函式既不是尾遞迴，也不是特別有效，其計算複雜度為O(2n)。此函式的尾遞迴形式的計算複雜度為O(n)。重寫上述函式，使其成為尾遞迴。
您可以使用以下內容驗證函式的正確性
fib(0I) = 0 fib(1I) = 1 fib(2I) = 1 fib(3I) = 2 fib(4I) = 3 fib(5I) = 5 fib(10I) = 55 fib(100I) = 354224848179261915075