1. Recursion
1.1 Definitions
Functions are packages of code that can be called by other programs and, of course, by the code inside the function. This way of calling the function itself from within the function definition is called recursion. It's like a person standing in a room full of mirrors, and the image they see is the result of recursion. Recursion is very powerful in math and computer applications and can solve important problems very succinctly.
A classic example of recursion in mathematics is called factorial, which is usually defined as follows.
n!= n(n- 1)(n- 2)…(1)
To implement this program, a simple circular accumulation can be used to compute the factorial. Observe that if 5! is removed from the computation, then it remains to compute 4!, and by extension, n! = n(n-1)! In fact, this relation gives another way of expressing the factorial:
When n = 0, n! = 1; otherwise, n! = n(n - 1)!
This definition states that the factorial of 0 is by definition 1, and the factorial of any other number is defined as that number multiplied by the factorial of a number 1 less than that number. Recursion is not a loop, because each recursion calculates the factorial of a number smaller than it until 0! 0! is a known value, known as the base case of recursion. When the recursion has reached the end, an expression is needed that can directly compute the value.
The factorial example reveals two key features of recursion:
(1) There exists one or more base cases, which do not need to be recursive again, and which are deterministic expressions.
(2) All recursive chains are to end in one or more base cases.
1.2 Mathematical induction
Both mathematical induction and recursion utilize the principle of recursion and are essentially the same. In proving a proposition P(n) with respect to natural numbers, mathematical induction uses the following steps.
(1) Show that the proposition holds when n takes the first value n0.
(2) Assume that the proposition holds when nk ( k ≥ 0, k is a natural number) and prove that it also holds when n = nk+1.
Combining (1) and (2), Proposition P(n) holds for all natural numbers n ( n ≥ n0).
2. Usage of recursion
2.1 The multiplication of steps
Taking the factorial calculation as an example, the factorial can be written as a separate function, which is then shown below:
def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
num = eval(input("Please enter an integer:"))
print(fact(abs(int(num))))
The fact() function references itself inside its definition, creating a recursive process (as in line 5). Unlimited recursion would exhaust computational resources, so it is necessary to devise a base case to make the recursion return level by level. fact() gives a base case for n being 0 by means of an if statement; when n==0, fact() stops recursing and returns the value 1, and if n!=0, it returns the product of n and the factorial of n-1 by recursion.
Since negative numbers and decimals cannot reach the base case of the recursion (n==0) by subtracting 1, line 8 of the code transforms the user input into a non-negative integer by using the abs() and int() functions, and the output of the program is as follows.
Please enter an integer: 5
120
Please enter a whole number: 6.789
720
Recursion follows the semantics of functions, where each call causes the start of a new function, indicating that it has copies of local variable values, including the function's arguments. At each function call, a copy of the function's arguments is stored temporarily, and each function in the recursion then operates on its own arguments without affecting each other. When the base case ends its operation and returns the value, each function ends its operation layer by layer and returns the result of its computation to the caller.
You must be careful with the construction of the base case when using recursion, otherwise the recursion will not be able to return and an error will be reported.
2.2 String inversion
For a user-entered string s, output the reversed string.
The basic idea in solving this problem is to think of a string as a recursive object. A long string is made up of shorter strings, and each smaller string is also an object. Suppose you think of a string as consisting of only two parts: the first character and the rest of the string. If you swap the remaining string with the first character, you have reversed the entire string, as shown in the following code:
def reverse(s):
return reverse((s[1:]) + s[0])
Observe how this function works. s[0] is the first character and s[1:] is the remaining string, concatenate them in reverse to get the reversed string. Execute this program with the following result.
def reverse(s):
return reverse(s[1:]) + s[0]
reverse("abc")
return reverse(s[1:]) + s[0]
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
This error indicates that the recursion created by the reverse() function could not be executed because the reverse() function has no base case and the number of levels of recursion exceeds the maximum recursion depth allowed. By default, the Python interpreter terminates the program when the recursion reaches 1000 levels. The recursion depth is designed to prevent infinite recursion errors, and can be set by the following code when the user writes a properly recursive program that requires more than 1000 levels:
import sys (2000) # 2000 is the new recursion level
reverse() exceeds the recursion depth because the base case was not designed. Recursive calls in string reversal always use a shorter string than before, so the base case can be designed to be the shortest form of the string, the empty string.
The full code is below:
def reverse(s):
if s == "":
return s
else:
return reverse(s[1:]) + s[0]
str = input("Please enter a string:")
print(reverse(str))
The results of the program execution are as follows:
Please enter a string: Python Programming
Design sequence nohtyP
3. Plotting of Koch curves
3.1 Summary
This is an example of a recursive approach to plotting Koch curves, where fractal geometry uses a recursion-like core idea.
There are many graphs in nature that are regular and conform to certain mathematical laws, for example, the honeycomb of a bee is a natural equilateral hexagon, etc. The Koch curve is very famous among the classical mathematical curves, which was proposed by the Swedish mathematician von Koch (H-V-Koch) in 1904. It was proposed by the Swedish mathematician H-V Koch in 1904, and is also known as the snowflake curve because of its shape, which resembles a snowflake.
The basic concepts and methods of plotting Koch curves are as follows:
The positive integer n represents the order of the Koch curve and indicates the number of operations in the process of generating the Koch curve. The Koch curve is initialized to order 0 and represents a straight line of length L. For a straight line L, it is divided into three equal segments. For the line L, it is divided into 3 segments, and the middle segment is replaced by two sides of an equilateral triangle of length L/3 to obtain a 1st order Koch curve, which contains 4 segments. Further repeat the same operation for each segment to obtain a 2nd order Koch curve. Continuing to repeat the same operation n times yields an nth order Koch curve as shown in the figure below:
3.2 Plotting the Koch Curve
The Koch curve belongs to the fractal geometry branch, its drawing process reflects the recursive idea, the drawing process code is as follows:
import turtle
def koch(size, n):
if n == 0:
(size)
else:
for angle in [0, 60, -120, 60]:
(angle)
koch(size / 3, n - 1)
def main():
(800, 400)
(0) # Control drawing speed
()
(-300, -50)
()
(2)
koch(600, 6) # Length of Koch curve of order 0, order
()
main()
The results of the program execution are as follows:
Drawing an nth order Koch curve is equivalent to drawing n-1st order curves at 0°, 60°, -120°, and 60° in the forward direction of the brush. The main() function in the above code sets some initial parameters, and if you want to control the speed of the Koch curve, you can use the () function to increase or decrease the speed.
3.3 Snowflake effect with Koch curves
The Koch curve starts with a straight line drawing, and would be more interesting if it started with an inverted triangle. Replace the main() function in the previous code with the following code:
import turtle
def koch(size, n):
if n == 0:
(size)
else:
for angle in [0, 60, -120, 60]:
(angle)
koch(size / 3, n - 1)
def main():
(600, 600)
(1000)
()
(-200, 100)
()
(2)
level = 5
koch(400, level)
(120)
koch(400, level)
(120)
koch(400, level)
()
main()
The results of the program execution are as follows:
3.4 Fractal geometry
Fractal geometry is a branch of mathematics that takes irregular geometric forms as its object of study. Fractals are based on self-similar structures and demonstrate the inherent mathematical order beneath complex surfaces by means of infinite recursion. Fractal geometry not only demonstrates the beauty of mathematics, but also reveals the nature of the world, making people re-examine the world: the world is non-linear and fractals are everywhere.
To this article on how to use Python to draw the Koch Curve is introduced to this article, more related Python Koch Curve content, please search for my previous articles or continue to browse the following related articles I hope you will support me in the future!