Function recursion and iteration

Author：AXYZdong Automation Engineering Male

1. Baidu Encyclopedia explains

recursive ：

The programming skill of the program call itself is called recursive （ recursion）. Recursion as an algorithm is widely used in programming languages . A procedure or function has a method that directly or indirectly calls itself in its definition or description , It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve , The recursion strategy only needs a few programs to describe the repeated calculation needed in the process of solving problems , Greatly reduces the amount of code in the program . The power of recursion is to define infinite sets of objects with finite statements . Generally speaking , Recursion needs boundary conditions 、 Recursive forward segment and recursive return segment . When the boundary conditions are not satisfied , Forward recursively ; When the boundary conditions are satisfied , Recursively returns .

iteration ：

Iteration is the activity of repeating the feedback process , Its purpose is usually to approach the desired goal or result . Every repetition of a process is called a “ iteration ”, The result of each iteration will be taken as the initial value of the next iteration .

Repeat a series of steps , The process of finding out the following quantity from the preceding quantity in turn . Every result of this process , They are all obtained by performing the same operation steps on the previous result . For example, the iterative method is used to find the solution of a mathematical problem .

For the subroutines that need to be executed repeatedly in a specific computer program ( A set of instructions ), Make a repeat , Repeat the loop in the program , Until certain conditions are met , Also known as iteration .

2. Other explanations

recursive （recursion）： Recursion is often used to describe the process of repeating things in a self similar way , In mathematics and Computer Science , It refers to the method of using function itself in function definition .（A call A）

iteration （iteration）： Activities that repeat the feedback process , The result of each iteration will be taken as the initial value of the next iteration .（A Repeated calls to B）

author ： Over there link ：https://www.jianshu.com/p/32bcc45efd32 source ： Simple books

recursive , It is to call itself in the process of running .

The conditions that constitute recursion ：

1. The sub problem must be the same thing as the original problem , And it's simpler ;
2. You can't call itself unlimited , There must be an exit , Reduction to non recursive state processing .

Iteration method is also called toss method , It is the process of recursing a new value from the old value of a variable , The counterpart of the iterative method is the direct method ( Or it's called the first solution ), Solve the problem once and for all .

author ： Nest enclosure 111 link ：https://blog.csdn.net/qq_40817827/article/details/89950325 source ：CSDN

3. Both comparisons

Recursion is a tree structure , Literally, it can be understood as repetition “ Recurrence ” and “ Return to ” The process of , When “ Recurrence ” When you reach the bottom, you start “ Return to ”, The process is equivalent to the depth first traversal of the tree .

Iteration is a ring structure , From the beginning , Every iteration goes through the loop , And update the status , Iterations until the end state is reached .

Theoretically, recursion and iteration time complexity are the same , But in practice （ The cost of function calls and function call stacks ） Recursion is less efficient than iteration .

Recursion and iteration structure diagram

The same thing ：

• Recursion and iteration are both A kind of circulation .

Difference ：

1、 The program structure is different

• Recursion is to repeatedly call the function itself to realize the loop .
• An iteration is a loop implemented by a piece of code in a function .
• among , The difference between an iteration and a normal loop is ： iteration , The variables involved in the operation in the loop code are the variables to save the results , The current saved result is the initial value of the next cycle calculation .
• The difference between recursion and normal loops is ： There is no return to the cycle , And recursion is going back ( Because there are termination conditions ).

2、 The algorithm ends in different ways

• Recursive loop , When the termination conditions are met, return layer by layer to end .
• The iteration ends the loop with a counter .

3、 Different efficiency

When the number of cycles is large , The efficiency of iteration is obviously higher than that of recursion .

4. example

The Fibonacci sequence is realized by recursion and iteration respectively

# -*- coding: utf-8 -*-
# @File :  recursive 
# @Author : axyzdong
# @Time : 2021/12/22
# @Description : Using recursion to realize Fibonacci sequence 
def recursion_fab(n):
    if n < 1:
        print(' Incorrect input ！')
        return -1
    if n == 1 or n == 2:
        return 1
    else:
        return recursion_fab(n - 1) + recursion_fab(n - 2)


recursion_month = int(input(' Please enter the number of months elapsed ：'))
recursion_num = recursion_fab(recursion_month)
if recursion_num != -1:
    print(' Recursive method ： after %d After month , The total number of rabbits is ：%d' % (recursion_month, recursion_num))

# -*- coding: utf-8 -*-
# @File :  iteration 
# @Author : axyzdong
# @Time : 2021/12/22
# @Description : Using iteration to realize Fibonacci sequence 
def iteration_fab(n):
    n1 = 1
    n2 = 1
    n3 = 2
    if n < 1:
        print(' Incorrect input ！')
        return -1
    if n == 1 or n == 2:
        return 1
    while (n - 2) > 0:
        n3 = n1 + n2
        n1 = n2
        n2 = n3
        n = n - 1
    return n3


iteration_month = int(input(' Please enter the number of months elapsed ：'))
iteration_num = iteration_fab(iteration_month)
if iteration_num != -1:
    print(' Iterative method ： after %d After month , The total number of rabbits is ：%d' % (iteration_month, iteration_num))

5. summary

• Recursion and iteration are both methods of function implementation , Contains different logical ideas ;
• Recursively and repeatedly call its own function , Programming ideas are relatively clear ;
• The iteration starts with the initial value of the variable , Keep pushing new values with old values of variables .

reference

1：https://blog.csdn.net/qq_40817827/article/details/89950325

2：https://www.jianshu.com/p/32bcc45efd32

3：https://blog.csdn.net/daijin888888/article/details/70157153

   This sharing is here