F＃理解遞歸函數

我想了解爲什麼遞歸函數的行爲方式是這樣。F＃理解遞歸函數

let rec fact = function 
    |0 -> 1 
    |n -> n * fact(n-1);;

在i執行：

fact 4;;

它響應：

val it : int = 24

這是ofcourse是正確的，因爲1 * 2 * 3 * 4 = 24

什麼我不't get this is piece of code：

|n -> n * fact(n-1);;

我不知道爲什麼它不計算：

4 -> 4 * (4-1) 
4 -> 4 * 3 
4 -> 12

我的猜測是我誤解n的定義

有人可以做到的榮譽和賜教？

來源

2016-02-18 Nulle

這不是計算4 * (4-1)，因爲代碼不是n * (n-1)。這是n * fact (n-1)，所以它計算4 * fact (4 - 1)，那就是：

4 * fact (4 - 1) 
= 4 * fact 3 
= 4 * (function | 0 -> 1 | n -> n * fact (n-1)) 3 
= 4 * (match 3 with | 0 -> 1 | n -> n * fact (n-1)) 
= 4 * 3 * fact (3 - 1) 
= 4 * 3 * fact 2 
...

，以此類推，直到你終於得到4 * 3 * 2 * 1 * fact 0 = 4 * 3 * 2 * 1 * 1 = 24。

來源

2016-02-18 14:00:45 sepp2k

我很難搞清楚在你說的「匹配3與...」這一點上發生了什麼，你能詳細說明一下嗎？ – Nulle

感謝您的幫助！非常有幫助！ – Nulle

如果定義爲n -> n * (n - 1)這將是真實的，但它正在爲fact遞歸調用因此它是：

4 * fact(4 - 1) 
=> 4 * fact(3) 
=> 4 * (3 * fact(2)) 
=> 4 * (3 * (2 * fact(1))) 
=> 4 * (3 * (2 * (1 * fact(0)))) 
=> 4 * (3 * (2 * (1 * 1))) 
=> 4 * (3 * (2 * 1)) 
=> 4 * (3 * 2) 
=> 4 * 6 
=> 24

來源

2016-02-18 14:01:06 Lee

我把它rec是什麼使我的函數遞歸，那麼爲什麼當我從我的代碼中刪除rec我仍然得到相同的結果？你說的一切都是有道理的。 – Nulle

@Nulle - 它是在'fact'函數內調用'fact'使其遞歸。 F＃要求使用'rec'聲明遞歸函數，以使函數名稱在聲明函數內可見。如果你只是刪除'rec'關鍵字，你應該得到一個編譯錯誤，說明沒有'fact'的定義。 – Lee

@Nulle'rec'是什麼*允許*您的函數是遞歸的。如果刪除它，除非有事先定義，否則應該會出錯。 – sepp2k

我想我現在弄明白了！

fact 4;; 
fun 4 match 4 with |0 -> 1|n -> n * fact(n-1) 
|0 -> 1|4 -> 4 * fact(4-1) 
|false |4 -> 4 * fact(3) 
|false |4 -> 4 * fun 3 match 3 with |0 -> 1|n -> n * fact(n-1) 
|false |4 -> 4 * |0 -> 1|3 -> 3 * fact(3-1) 
|false |4 -> 4 * |false |3 -> 3 * fact(2) 
|false |4 -> 4 * |false |3 -> 3 * fun 2 match 2 with |0 -> 1|n -> n * fact(n-1) 
|false |4 -> 4 * |false |3 -> 3 * |0 -> 1|2 -> 2 * fact(2-1) 
|false |4 -> 4 * |false |3 -> 3 * |false |2 -> 2 * fact(1) 
|false |4 -> 4 * |false |3 -> 3 * |false |2 -> 2 * fun 1 match 1 with |0 -> 1|n -> n * fact(n-1) 
|false |4 -> 4 * |false |3 -> 3 * |false |2 -> 2 * |0 -> 1|1 -> 1 * fact(1-1) 
|false |4 -> 4 * |false |3 -> 3 * |false |2 -> 2 * |false |1 -> 1 * fact(0) 
|false |4 -> 4 * |false |3 -> 3 * |false |2 -> 2 * |false |1 -> 1 * fun 0 match 0 with |0 -> 1|n -> n * fact(n-1) 
|false |4 -> 4 * |false |3 -> 3 * |false |2 -> 2 * |false |1 -> 1 * |true| 
4 -> 4 * 3 -> 3 * 2 -> 2 * 1 -> 1 * 0 -> 1 = 24

來源

2016-02-18 15:31:04 Nulle

F＃理解遞歸函數

回答

相關問題