遞歸序列的迭代方法

Question

如何解決遞歸序列a（n）= - a（n-1）+ n-1？ 我試過向前和向後的迭代，但一直沒有能夠得到明確的解決方案（n）。

Answer 1

你的第一步應該是寫出來的結果表

f(n)=x 

n | x 
----- 
0 | 7 
1 | -7  (-7 + 1 - 1) 
2 | 8  (7 + 2 - 1) 
3 | -6  (-8 + 3 - 1) 
4 | 9  (6 + 4 - 1) 
5 | -5  (-9 + 5 - 1) 
6 | 10  (5 + 6 - 1) 
7 | -4  (-10 + 7 - 1) 
8 | 11  (4 + 8 - 1) 
9 | -3  (-11 + 9 - 1) 

你應該看到一個模式不斷涌現。每對解決方案[(0, 1), (2, 3), (4, 5), ...]的差異爲14，從(7, -7)開始，並遞增n的每兩個點。我們可以這樣概括：

f(0) = 7 
f(n) = 7 + k - 14 * b 
    where k is the increment value (each 1 k per 2 n) 
     b is 1 when n is odd, else 0. 

現在我們只需要在n來定義k和b。 k不要太辛苦，讓我們來看看：

n | k 
0 | 0 
1 | 0 
2 | 1 
3 | 1 

這是否讓你想起什麼？這是一個地板div2。

7 + (n // 2) - 14 * b 

現在對於b

n | b 
0 | 0 
1 | 1 
2 | 0 
3 | 1 

這看起來像mod 2給我！模數是分裂問題的其餘部分，並且是檢查數字是偶數還是奇數的好方法。我們也在尋找普通的模數，因爲我們想，當n是奇數，反之亦然。

f(0) = 7 
f(n) = 7 + (n // 2) - 14 * (n%2) 
    where (//) is the floor division function 
     (%) is the modulo function 

---

現在我們可以把所有的一起在一個功能。在圍棋是這樣的：

func f(n int) int { 
    return 7 + n/2 - 14 * (n % 2) 
} 

在Python它的

def f(n): 
    return 7 + n//2 - 14 * (n%2) 

在Haskell我們已經有了

f :: Int -> Int 
f n = 7 + n `div` 2 - 14 * (n `mod` 2) 

，或者因爲哈斯克爾實現遞歸非常很好，只是......

f :: Int -> Int 
f 0 = 7 
f n = f (n-1) + n - 1