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

奇数列 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

原来求和公式就是：

def Sn(n)
    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

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

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

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

（本文完） 

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系