从斐波那契数列求和想到的俗手、本手和妙手

数列求和的通常做法，用先求出数列的通项公式，然后循环累加求和。先以奇数集求和为例：

奇数列 fn = 2n-1，通项公式及求和公式都写成函数，即：

def fn(n):
    return 2*n-1
def Sn(n):
    s = 0
    for i in range(1,n+1):
        s += fn(i)
    return s

测试：

>>> Sn(5)

25

>>> Sn(7)

49

>>> Sn(10)

100

原来求和公式就是：

1. def Sn(n)
2.     return n*n

同样，斐波那契数列求和也如此，最容易想到的就是用递归法写出通项公式，然后循环累加求和，和前面提到的奇数列公式套路都是一样的：

def F(n):
    if n in [1,2]: return 1
    return F(n-1) + F(n-2)
def Sn(n):
    s = 0
    for i in range(1,n+1):
        s += F(i)
    return s

然而学过数列的都会做以下推导：

   f1 = 1

   f2 = f1    

   f3 = f2 + f1

   f4 = f3 + f2

   f5 = f4 + f3

   f6 = f5 + f4

   ...  ...

   fn = f(n-1)+f(n-2)

以上各式累加，即可得到斐波那契数列之和的通项式：

Sn = 1+S(n-1) + S(n-2)

对比一下，数列通项和求和通项的异同，很美很对称的数学公式：

def F(n):
    if n in [1,2]: return 1
    return F(n-1) + F(n-2)
def S(n):
    if n in [1,2]: return n
    return S(n-1) + S(n-2) + 1

如此经典看似已经找到了本手，可惜的是此法算到40项左右就已经巨慢无比了，所以递归法就是一步俗手，中看不中用，实用性不高。这里要提一下改进型递归的尾递归法：

def fib(n, f1=1, f2=1):
  if n == 1: return f1
  return fib(n-1, f2, f1+f2)
def sib(n, s1=1, s2=2):
  if n == 1: return s1
  return sib(n-1, s2, 1+s1+s2)

速度提升不少，可以也只能算到1000项上下，再多了就会报递归深度超限的错：RecursionError:

maximum recursion depth exceeded in comparison。具体最多能算到哪一项与电脑的硬件性能有关。 关于递归法的优化方法还有很多，比如用把中间步骤写入列表等等；我以前也写过一篇关于斐数列递归优化方面的探讨，见：

Python 改进斐波那契数列递归后，计算第1000万项只需4秒_Hann Yang的博客-CSDN博客上一篇《不自己试试，还真猜不出递归函数的时间复杂度！》中写了一个递归函数求斐波那切数列某一项的值，号称它是终极改进了，但它有一个缺点：偶数项比奇数项算得慢。今天实然想到应该把偶数项也转换成奇数项来算，就会成倍提高运算速度：原理是这样的：F(2n)=F(n)*(F(n+1)+F(n-1)) ;

F(2n+1)=F²(n+1)+F²(n)偶数项需要三个项递归计算，奇数项只有两个项要递归。但是想到另外有公式可以把偶数项转换成奇数项：∵ F(2n)=F(2n+1)-F(2n-1)∴

F..https://hannyang.blog.csdn.net/article/details/120257133

从尾递归的参数调用看出它已经有点递推的意思在了，也就是说尾递归是递推加递归的结合。而全递推法没有递归深度的顾虑，算10万项之和也秒出结果，这才是本手：

def f(n):
  f1,f2 = 1,1
  for _ in range(2,n+1):
    f1,f2 = f2,f1+f2
  return f1
def sf(n):
  s,f1,f2 = 1,1,1
  for _ in range(2,n+1):
    f1,f2 = f2,f1+f2
    s += f1
  return s
def s(n): #改进型
  s1,s2 = 1,2
  for _ in range(2,n+1):
    s1,s2 = s2,1+s1+s2
  return s1

看似到这里应该啰嗦完了，但是峰回路转我在推导过程中还不经意地发现了一点小意外，堪称一步妙手，推导过程如下：

   Sn = 1+S(n-1) + S(n-2)

   Sn + fn + f(n-1) + fn  = 1+ 1+S(n-1)+fn + S(n-2)+f(n-1)+fn

   Sn + fn + f(n-1) + fn  = 1+ Sn + Sn

   f(n+1) + fn = 1+ Sn

   Sn = f(n+2) - 1

哦哦，原来求和公式与通项公式之间还有这层关系，马上测试一下公式的正确性：

def f(n):
  f1,f2 = 1,1
  for _ in range(2,n+1):
    f1,f2 = f2,f1+f2
  return f1
def s(n):
  return f(n+2)-1
for i in range(1,1001):
  if s(i)!=sf(i):print('error')
else:
  print('all clear')
#输出： all clear

所以，对斐波那契数列求和，称得上“神之一手”级别的函数是：

1. def S(n):
2.  f1,f2 = 1,1
3.  for _ in range(2,n+3):
4.    f1,f2 = f2,f1+f2
5.  return f1 - 1

由内比公式，我们还可以得出：

（本文完）