People who have experience in programming must be familiar with recursive functions. We often use recursion to solve a series of complex problems. Recursive algorithms are very effective for most problems, and they can also optimize our code. We There are a few things to note when using recursion:
1) Recursion is calling the function itself within the function itself.
2) The efficiency of recursion is relatively low, and it is not recommended to use it if there is a time limit.
3) There needs to be a clear end condition in the recursive process, that is, the recursive exit.
Let's explain recursive functions in detail below.
Let's first look at the simple use of recursion through an example:
m=int(input('Enter a number:'))deftest(x):x+=2ifx<100:test(x)else:print('The last x is:',x)test(m)The output is:
Enter a number: 20 and the last x is: 100
Let's analyze this example. First, in the first line of code, we input an integer. In the last line, m is passed as an actual parameter to the test() method. In the test() method, x will be added by 2 first, and then A judgment, if the value of x is less than 100, then call this function again. When calling, the current value of x is used as the actual parameter to participate in the call. The recursion ends when x>=100 is satisfied.
Look at the diagram below:
That is, if the conditions are not met, it returns to the outermost layer and calls this function.
When talking about classic problems in recursive algorithms, the Fibonacci sequence and the Tower of Hanoi are always inseparable. Here we will explain how to use recursion to solve the Fibonacci sequence.
First of all, we need to know that the recursive formula of the Fibonacci sequence is F(n)=F(n-1)+F(n-2), F(1), and F(2) are 1. We can use recursion To find the value of an item in the Fibonacci sequence.
There are many ways we can use to solve Fibonacci sequence problems.
First we use the commonly used recursive method to solve this problem:
N=int(input(input the number of items to be obtained:))deffibonacci(n):ifn<=2:#If it is less than or equal to 2, set n to 1 return1else:returnfibonacci(n-1)+fibonacci(n-2)print ('The corresponding value is',fibonacci(n))The output is:
Enter the number of items you want to get: 4 corresponds to 3
For this recursive calling method, when we enter the value 4, the following operations will be performed recursively:
fibonacci(3)+fibonacci(2)=fibonacci(2)+fibonacci(1)+fibonacci(2)
Then we can see that the value of the fourth term is 1+1+1=3.
In fact, this method of solving is a waste of time because too many iterations are required. We can also use space instead of time to solve this problem.
The code is as follows:
n=int(input(input the number of terms to be obtained:))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print(' The corresponding value is',fibonacci[n-1])The output is:
Enter the number of items you want to get: 4 corresponds to 3
In this way, we first specify the values of the first two items in the list, and then for the number n of items we want to solve, we directly fill the list of Fibonacci numbers to the item we need through the formula, and finally according to the index The value directly finds the corresponding output result.
That’s it for the recursive function. As mentioned above, we should pay special attention to the recursive exit and time limits. The exit is the key to the end of the recursion. In many cases, our use of recursive methods will cause the program to exceed the specified time. , at this time we need to change our thinking to solve the problem. The second method mentioned above can help everyone solve the problem.