Recursive method | Fibonacci sequence

Recursive method ：

Simplify the problem , Step-by-step , One by one 、 Until it can be solved , A step you can take . Finally, it turns into a simple problem .

It can call itself directly or indirectly ： 

Call directly or indirectly sum（） Oneself ：

python：

In[1]

def listsum(a):  

    if len(a) == 1:        

     return a[0] # If there is only one element in the list , Then return to a[0]   

   else:          

     return a[0] + listsum(a[1:]) # Returns the sum of the first element and the remaining other elements

print(listsum([1,3,5,7,9,13]))

Out[2]:

38

Introduction to Fibonacci sequence ：

Fibonacci sequence , also called ‘ Rabbit Series / Golden section series ’.

Characteristic 1 ：
Any number is the sum of the first two numbers .

for example ：

So the first way to calculate Fibonacci sequence , That is to add the last two elements of the number sequence , Get a new number and insert it at the end of the sequence .

Characteristic 2 ：
In the limit condition , The quotient of two adjacent elements is equal to a constant . namely

The first one is ：
So we can set an array .

a = [0,1]

The next data to insert is “a【-1】+a【-2】”.

a.append(a[-1] + a[-2])

Continue to cycle . loop y Once you get y A new number .

Finally, the number of numbers in the Fibonacci sequence is n = y + 2 .

According to the number of Fibonacci numbers the user wants n To define the number of cycles y.

y = n - 2

Input 【1】：

def fibs1(n): # Define the Fibonacci function    a = [0] # Statement a Is an array    if n <= 0:        print(' error ') #n You can't <= 0    else:        if n > 1:            a = [0,1]            for i in range(n - 2): # perform n-2 Secondary cycle , Immediate array a Newly added n-2 A Fibonacci number                a.append(a[-2] + a[-1]) # New figures = The sum of the last two numbers    return a

Input 【2】：

fibs1（10）

Output 【2】：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

The second kind ：
Define the number of elements in the array in advance , Then set each value as the sum of the first two numbers .

Input 【1】：

def fibs2(n): #n For the number of Fibonacci numbers needed    f = [0] * n # The definition contains n individual 0 Array of    if n <= 0:        print(' error ') #n You can't <= 0    else:       if n >= 2:            f[1] =1 # here f = [0 , 1]            for i in range(2,n):                f[i] = f[i - 1] +f[i-2]            '''            f[2] = f[1] + f[0] = 1, here f = [0,1,1]; Three Fibonacci numbers            f[3] = f[2] + f[1] = 2, here f = [0,1,1,2]; Four Fibonacci numbers             ......            f[n-1] = f[n-2] + f[n-1];n A Fibonacci number            '''    return f

Input 【2】：

fibs2（10）

Output 【2】：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Comparison of the running time of the two methods ：
Input 【1】：

%timeit fibs1(100)%timeit fibs2(100)

Output 【1】：

26.2 µs ± 736 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)30.7 µs ± 301 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)