The common hand, the original hand and the excellent hand from the sum of Fibonacci sequence

The usual practice of summing a sequence of numbers , First find out the general term formula of the sequence , Then circularly accumulate and sum . First, take the sum of odd sets as an example ：

Odd columns fn = 2n-1, Both the general term formula and the summation formula are written as functions , namely ：

def fn(n):
    return 2*n-1

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

test ：

>>> Sn(5)
25
>>> Sn(7)
49
>>> Sn(10)
100

The original summation formula is ：

def Sn(n)
    return n*n

Again , So is the sum of Fibonacci sequence , The easiest thing to think of is to write a general term formula by recursion , Then circularly accumulate and sum , It is the same as the odd column formula mentioned above ：

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

However, those who have learned the sequence of numbers will do the following derivation ：

f1 = 1
f2 = f1    
f3 = f2 + f1
f4 = f3 + f2
f5 = f4 + f3
f6 = f5 + f4
...  ...
fn = f(n-1)+f(n-2)

The above formulas add up , Then we can get the general term formula of the sum of Fibonacci sequence ：

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

Compare the , Similarities and differences between general term of the sequence and general term of the summation , A beautiful and symmetrical mathematical formula ：

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

Such a classic seems to have been found My hand , It is a pity that this method can reach 40 It is already extremely slow around the item , So recursion is one step Vulgar hand , Look and feel , Not very practical . Here we will mention the tail recursion method of improved recursion ：

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)

The speed increased a lot , It can only be counted as 1000 Upper and lower items , More than that, you will report an error that the recursion depth exceeds the limit ：RecursionError: maximum recursion depth exceeded in comparison. The most specific one is related to the hardware performance of the computer . There are many other optimization methods for recursive method , For example, write the intermediate steps into the list, etc ; I have also written a discussion on recursive optimization of the feynold sequence , see ：

Python After improving the recursion of Fibonacci sequence , Computation first 1000 Ten thousand items only need 4 second _Hann Yang The blog of -CSDN Blog Last one 《 No, try it yourself , I really can't guess the time complexity of recursive functions ！》 A recursive function is written to find the value of a term in the Fibonacci sequence , It claims to be the ultimate improvement , But it has one drawback ： Even terms count slower than odd terms . Today, I actually thought that I should convert even items into odd items , It will multiply the computing speed ： The principle is ：F(2n)=F(n)*(F(n+1)+F(n-1)) ; F(2n+1)=F²(n+1)+F²(n) Even items require three items to be calculated recursively , Odd items have only two items to recurse . But think of another formula that can convert even terms into odd terms ：∵ F(2n)=F(2n+1)-F(2n-1)∴ F..https://hannyang.blog.csdn.net/article/details/120257133
From the parameter call of tail recursion, we can see that it has a little recursive meaning , That is to say, tail recursion is a combination of recursion and recursion . The full recursive method has no concern about the depth of recursion , count 10 The sum of ten thousand items also produces results in seconds , That's what it is. My hand ：

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): # Improved 
	s1,s2 = 1,2
	for _ in range(2,n+1):
		s1,s2 = s2,1+s1+s2
	return s1

It seems that I should have finished talking here , But the twists and turns of the road, I also inadvertently found a little accident in the derivation process , One step A good hand , The derivation process is as follows ：

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

Oh oh , It turns out that there is this relationship between the summation formula and the general term formula , Test the correctness of the formula immediately ：

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')

	
# Output ： all clear

therefore , Sum the Fibonacci sequence , It can be called “ One hand of God ” The level function is ：

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

（ The end of this paper ）