Make writing a habit together! This is the second day of my participation in the “Gold Digging Day New Plan · April More text challenge”. Click here for more details.

1 recursive call

Although recursion can solve some difficult problems quickly, it is difficult to master recursion because of its abstractness. Although I have explained the recursion example in “Recursion Basics”, and have a simple understanding of the call process of recursion, BUT lack of specific cognition. This section takes a closer look at recursive calls.

When a recursive function is executed, each recursive call creates a new copy of the function in memory. Once the function call ends, some data is returned and the copy is deleted from memory. Often, the recursive approach results in a solution that looks simple and simple, but understanding and tracking the execution of the function is complicated. To better understand, consider the following simple example of finding a 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()
Copy the code

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

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 active record is created and a new copy of local variables is stored in the active record. The sequence of calls during the program run is shown in the following figure:

When the function executes to n=0, the fibo() function returns its first value, which returns 1 to the previous function call. As shown in the figure below, the active record of the function call at n=0 pops up from the runtime stack (indicated by graying the active record in the figure). When the function returns, the space for the active record is reclaimed for later use. The Shadowed object 0 on the heap is also reclaimed by the garbage collector because there is no longer a reference to it.

After the first fibo() function returns, 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 value of 1. Again, the function returns, but this time with a value of 2. Follow the above process until fibo() returns to line 8 of main(), as shown below:

Finally, the program prints the execution, returns from main() after line 9, and terminates from module after line 11. As you can see from the example above, 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 into the corresponding active record. When the function call returns, the corresponding activity record pops up from the runtime stack. That’s how recursive functions work.

Recursive visualization

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

2.1 Turtle Library Introduction

The Turtle library is python’s standard library, usually used for drawing patterns. You can use the library to create a turtle moving on the canvas. When the turtle crawls, it draws lines on the canvas, but when the tail is raised, it does not draw.

Next, we’ll cover some basic Turtle drawing functions:

  • Turtle.penup (): Turtle raises its tail, and subsequent movements are not plotted on the diagram
  • Turtle.pendown () : Turtle lowers its tail and begins to crawl, then plots its movements on a graph
  • Turtle.pensize (width) : Used to change the width of the brush
  • Turtle.pencolor (color) : Used to change the color of the brush
  • Turtle. forward(distance) : Moves the distance forward
  • Turtle. back(distance) : Move distance backwards

2.1 Recursive plotting

Get to know the Turtle library by creating a simple recursive function draw(). The basic case of this recursive function is that the distance to draw is reduced to 0; If the line is larger than 0, let the turtle draw distance units forward and turn left 30 degrees. The recursion is — the shortened distance calls draw() again.

# Import turtle library
import turtle
# create a turtle object
my_turtle = turtle.Turtle()
Create a window for the user to draw patterns
window = my_turtle.getscreen()

def draw(turtle, distance) :
    if distance > 0:
        # Turtle 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()
Copy the code

A link to the

Python algorithms — recursion