递归序列的迭代方法

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