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

Today, the editor will share with you the relevant knowledge points of the recursive visualization method of Python data structure, the content is detailed, and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this 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. Although some difficult problems can be solved quickly by using recursion, it is difficult to master recursion because of its abstraction. In order to better understand the idea behind the recursive function, this section mainly understands the execution steps of the recursive function through visualization.

two。 Recursive call

Although some difficult problems can be solved quickly by using recursion, it is difficult to master recursion because of its abstractness. Although the example of recursion has been explained in "Recursive fundamentals" and a simple understanding of the calling process of recursion, there is a lack of specific knowledge. This section provides a more in-depth explanation of recursive calls.

When a recursive function executes, each recursive call creates a new copy of the function in memory, and once the function call ends, some data is returned and the copy is deleted from memory. In general, the solution obtained by the recursive method looks simple and simple, but it is more complex to understand and track the execution of the function. For a better understanding, consider the following simple example of finding the Fibonacci sequence:

Def fibo (n): if n = = 0: return 1 else: return n * fibo (n-1) def main (): number = 4 result = fibo (number) print (result) if _ name__ = = "_ main__": main ()

When the program runs to line 10. The first call to the fibo () function creates a new activity record for the fibo () function call, with three activity records on the runtime stack. Then the Python interpreter jumps to line 2, where n points to the number 4, as shown in the following figure. N is not equal to 0, so jump to line 5, which contains a function call to fibo (), which creates another activity record on the runtime stack. Repeat the above process until n = 0.

It is important to note that each recursive function call has a copy of the variable n. The active record holds all local variables and parameters within the scope of the function. Each time a function is called, a new activity record is created, and a new copy of the local variable is stored in the activity record. The calling sequence of the program running process is shown in the following figure:

When the function executes to n _ zero, the fibo () function returns its first value, which returns 1 to the previous function call. As shown in the following figure, the activity record of the function call when nroom0 is popped from the runtime stack (represented by graying the activity record in the diagram). When the function returns, the space of the active record is reclaimed for later use. The shadow object 0 on the heap is also reclaimed by the garbage collector because there are no more references to it.

After the first return of the fibo () function, the Python interpreter returns to line 5 of the previous function call, which also contains a return statement, so the function returns to line 5 again with a return value of 1. Again, the function returns again, but this time the value is 2. Follow the above procedure until the fibo () function returns to line 8 of the main () function, as shown in the figure below:

Finally, the program prints the execution result, returns from the main () function after line 9, returns from module after line 11 and terminates. As you can see from the above example, each recursive call to the fibo () function creates its own copy of the variable. Each time the function is called, local variables and parameters are copied to the corresponding activity record. When the function call returns, the corresponding activity record pops up from the runtime stack. This is how recursive functions are executed.

3. Recursive visualization

This section will use the recursive drawing pattern of the turtle library to improve the understanding of the recursive process.

3.1 introduction to turtle Library

The turtle library is a standard library for python and is usually used to draw patterns. You can use this library to create a turtle that moves on the canvas and draws lines on the canvas as the turtle crawls, but not when the current tail is raised.

Next, we will introduce some basic turtle drawing functions:

Turtle.penup (): turtle raises his tail, and the subsequent movement is not drawn on the diagram

Turtle.pendown (): turtle puts down his tail, starts crawling, and then draws his trajectory on the graph.

Turtle.pensize (width): used to change the width of the brush

Turtle.pencolor (color): used to change brush color

Turtle.forward (distance): move distance forward

Turtle.back (distance): move distance backwards

3.1 Recursive drawing

First of all, we can understand the turtle library by creating a simple recursive function draw (). The basic situation of this recursive function is that the line length distance to be drawn is reduced to 0; if the line length is greater than 0, let the little tortoise draw distance unit distance forward, and then turn left 30 degrees; recursive case is-the shortened distance is called the draw () function again.

# Import turtle library import turtle# to create Little Tortoise object my_turtle = turtle.Turtle () # create a window for users to draw patterns window = my_turtle.getscreen () def draw (turtle, distance): if distance > 0: # Little Tortoise draws distance units forward turtle.forward (distance) # then turn left 30 degrees turtle.left (30) draw (turtle, distance-6) draw (my_turtle 200) window.exitonclick ()

Next, we use the turtle module to draw the fractal tree. Fractal tree and recursion have a lot in common, which is a concept in mathematics. No matter how many times you magnify the fractal graph, you can always see the same basic shape.

If we define a tree as a subtree that contains a subtree growing to the left and a subtree growing to the right, we can get a fractal tree according to the idea of recursion:

Import turtledef tree (branch, turtle): if branch > 5: turtle.forward (branch) turtle.right (20) tree (branch-15, turtle) turtle.left (40) tree (branch-10 Turtle) turtle.right (20) turtle.backward (branch) my_turtle = turtle.Turtle () window = my_turtle.getscreen () my_turtle.left (90) my_turtle.up () my_turtle.backward (300) my_turtle.down () tree (110, my_turtle) window.exitonclick () above are all the contents of the article "Recursive Visualization of Python data structures" Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to 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.