SML：如何使用+1和-1遞歸地減半整數n

Question

如何在SML中遞歸地分割數字n？

fun halves (n : int) : int * int = 
    let val x = 0 
    val y = x+1 
    in 
    case n of 
    x => (n,x) 
    |y => (n,y) 
    |_ => halves(n-1) 
    end 

Answer 1

這是一個功課題嗎？

您發佈的代碼沒有意義，因爲三種情況是多餘的：模式「x」匹配所有內容，「y」也匹配，「_」也匹配。如果你想檢查0，只需在模式中寫入0。在你的代碼中，x的值總是0，y總是爲1.

這是一個提示：如果你有兩個互相調用的函數（相互遞歸）會怎麼樣？您可以定義那些好玩...，像：

fun f (a, b) = g (b, a) 
and g (a, b) = f (a + b, a - b) 

（當然，這只是循環永遠）。

Answer 2

你應該仔細考慮你的基礎和你的遞歸步驟。

的依據很簡單：halves 0 = (0,0)

對於遞歸步驟 - 問問自己，你將如何如使用halves 11 = (5,6)來計算halves 12的事實？同樣，你會如何使用halves 12 = (6,6)來計算halves 13的事實？一般來說，如果你讓(a,b)爲halves (n-1)，就a和b而言，什麼是halves n？