Shulou(Shulou.com)05/31 Report--

Most people do not understand the knowledge points of this article "how to use the recursive method of Python data structure", so the editor summarizes the following content, detailed content, clear steps, and has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "how to use the recursive method of Python data structure" article.

1. Learning goal

Recursive functions are those that call themselves directly or indirectly through a series of statements. Recursion plays an important role in programming. In many cases, problems can be solved elegantly with the help of recursion. This section focuses on the basic concepts of recursion and how to build recursive programs.

two。 Recursion 2.1 basic concept of Recursion

Recursion is a way to solve a problem, which constantly divides the problem into smaller sub-problems and solves the problem by dealing with ordinary sub-problems. Recursive functions are those that call themselves directly or indirectly through a series of statements. It should be noted that each time the recursive function calls itself, the original problem will be simplified, and finally the sequence of smaller problems must converge to the basic situation, solve the problem, and stop recursion. Some complex problems can be solved elegantly by using recursion. Many mathematical functions are defined recursively, such as factorial functions defined recursively:

Although this definition is recursive, it is not an infinite loop that cannot be terminated. In fact, factorial can be easily calculated by using this function. For example, if we calculate 3 cycles, according to the definition, there are 3 cycles 3 (3 − 1)! = 3 (2!), then we need to solve the problem of 2 cycles, apply the definition 3 colors = 4 (2!) = 3 [(2) (2) 1)!] = 3 (2) (1!) again, and continue this process. Finally, we need to calculate 0 cycles, and according to the definition of 0 cycles 1, the calculation process is over:

3 (2!) = 3 (2) (1!) = 3 (2) (1) (0!) = 3 (2) (1) (1) = 6

As you can see, the recursive definition is not infinitely circular, because each time the definition is applied, the program decomposes the problem into simpler sub-problems. In the example of a factorial function, the factorial of a smaller number is calculated until zero is calculated. This can be solved without applying recursion again. When recursive to the end, we get a closed expression that can be calculated directly, also known as the "basic case" of recursion. When a function calls itself to perform a subtask, it is called a "recursive case".

2.2 importance of Recursion

Recursive function is an important programming technique borrowed from mathematics. Recursion is usually used to greatly reduce the amount of code, and it is very useful in many tasks that can be decomposed into sub-problems, for example, sorting, traversal and search can usually give solutions quickly with the help of recursive methods.

2.3 three principles of Recursion

Like many algorithms, recursion also has important principles to follow, called the three principles of recursion:

Recursive algorithms must have basic conditions.

The recursive algorithm must change the state and gradually converge to the basic situation.

The recursive algorithm must include recursive cases and can call itself recursively.

It is important to note that the core idea of recursion is not a loop, but to break down the problem into smaller, easier-to-solve sub-problems.

2.4 Application of Recursion

Recursion plays a very important role in programming. Here are some practical scenarios that are commonly used to recursion:

Mathematical problems such as Fibonacci sequence and factorial calculation

Merge sort, quick sort

Binary search

Traversal of trees and graphs and related problems

Hanoi Tower

3. Recursive example

In this section, we will start with a simple list sum problem, understand the use of recursive algorithms, and then learn how to solve the classical recursive problem-the Tower of Hanoi.

3.1 list summation

List summation is a very simple problem, and it is more appropriate to understand the idea of recursive algorithms. For example, we need to calculate the sum of the list [1, 2, 3, 4, 5]. If we use a loop function, we can write the following code to calculate the sum of all the numbers in the list:

Def sum_list (list_data): result = 0 for i in range (list_data): result + = i return result

If we don't use loops, how can we solve this problem? We can write the summation process (1x2) + 3) + 4) + 5), and according to the additive exchange law, the calculation process can also be written as (1 + (2 + (3 + (4 + 5). Then we can clearly see that the sum of the data in the list is equal to the first element of the list plus the rest of the list:

Use python to implement the above equation as follows:

Def sum_list (list_data): if len (num_list) = = 1: return list_data [0] else: return list_data [0] + sum_list (list_ data [1:])

In the code, the condition for the exit of the function is first given, which is the basic case of the recursive function. In the example, the element sum of a list of length 1 is the number in the list. If the exit condition is not met, sum_list will call itself, which is the recursive case of a recursive function and why it is called a recursive function.

In figure (a) below, you can see the recursive invocation process when solving [1, 2, 3, 4, 5]. Each recursive call is solving a problem that is closer to the basic situation until the problem cannot be further simplified.

When the problem cannot be simplified, begin to piece together the solutions of all the sub-problems. The following figure (b) shows the addition of the recursive function sum_list when it returns the results of a series of calls. When it returns to the top level, the initial problem is solved.

3.2The problem of Towers of Hanoi

The Tower of Hanoi (Towers of Hanoi) is a classic puzzle. It consists of three towers and many discs of different sizes, which can be moved to any rod. At the beginning, the discs are arranged on a tower in ascending order, with the smallest at the top and the largest at the bottom. The goal of the puzzle is to move the folded disc to another pole and meet the following rules:

You can only move one disk at a time.

A larger disk cannot be placed on a smaller disk.

Next, we will show how to move a stack of disks with a height of n from the starting tower Source to the terminal tower Destination with the help of an intermediate tower Auxiliary:

With the help of the terminal tower Destination, move the top n-1 disc from Source to Auxiliary

Move the nth disc from the Source tower to the terminal tower Destination

Move n-1 disks from the secondary tower Auxiliary to the terminal tower Destination with the help of the Source tower

The above steps can be performed recursively as long as the movement rules of the Tower of Hanoi are followed. The simplest tower of Hanoi is that there is only one plate. In this case, just move the plate to the end post Destination. This is the basic situation. The above recursive steps approach the basic situation by gradually decreasing the height n, as shown in the following figure:

The key of the algorithm is to make two recursive calls. The first recursion is to move all the disks except the last disk from the Source tower to the auxiliary tower Auxiliary. Then move the last disk to the terminal tower Destination. The second recursion is to move the disk from Auxiliary to Destination:

Def towersOfHanoi (number, source=1, destination=3, auxiliary=2): if number > = 1: towersOfHanoi (number-1, source, auxiliary, destination) print ("Move disk% d from tower% d to tower% d"% (number, source, destination) towersOfHanoi (number-1, auxiliary, destination, source) towersOfHanoi (number=3)

The program output is as follows:

Move disk 1 from tower 1 to tower 3

Move disk 2 from tower 1 to tower 2

Move disk 1 from tower 3 to tower 2

Move disk 3 from tower 1 to tower 3

Move disk 1 from tower 2 to tower 1

Move disk 2 from tower 2 to tower 3

Move disk 1 from tower 1 to tower 3

The above is about the content of this article "how to use the recursive method of Python data structure". I believe we all have a certain understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about the relevant knowledge, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.