Deeply grasp recursive thinking and unlock the magical world of programming
1. What is Recursion? An Old Story Tells You
“Once upon a time, there was a mountain, and on the mountain, there was an old monk telling a story to a young monk, and the story was: once upon a time, there was a mountain, and on the mountain, there was an old monk telling a story to a young monk…”
This infinite loop of a story is a perfect metaphor for recursion! In programming, recursion is the process of a function calling itself, just like the continuously nested plot in the story.
What is recursion?
It is essentially like a Russian doll.
2. Recursion vs Loop: Different Personalities of Twins
# Loop example
for i in range(100):
print(f"This is the {i}th loop")
# Recursion example
def recursive_func(n):
if n > 0:
print(f"This is the {n}th recursive call")
recursive_func(n-1)
Key differences:
-
Loop: Variable changes, executing the same code block
-
Recursion: Function self-calls, each time with different parameters, forming a call stack
3. Core Thinking of Recursion: Three Steps to Build a Recursive Function
def recursive_function(parameters):
if condition_to_stop: # Must exist! Otherwise, infinite recursion
return termination_result
process_current_layer_logic
recursive_call(modified_parameters) # Move towards a smaller problem size
assemble_result_returnThe thinking of recursion is somewhat similar to loops, but unlike loops: in loops, the parameter variable changes while the code executed remains the same;
for i in range(10): # i increases by 1 each loopWhereas recursion is when a function is “calling itself”, and within that “self”, there is another “self”, just like a Russian doll. As long as the condition is met, it can continuously call “itself”, and the parameter variable can be different each time.
4. Classic Recursion Case Collection
| Case Name | Feature Description | Application Scenario |
|---|---|---|
| Fibonacci Sequence | F(n)=F(n-1)+F(n-2) | Algorithm problems, mathematical models |
| Tower of Hanoi | Moving disks via an intermediary pole | Teaching divide and conquer algorithms |
| Recursive Tree Drawing | Self-similarity of branch bifurcation | Computer graphics |
| Sierpiński Triangle | Infinitely self-similar fractal structure | Fractal geometry visualization |
5. Practical: Drawing a Magical Spiral with Recursion (Turtle Version)
from turtle import *
def draw_spiral(L):
if L < 300: # Termination condition
forward(L)
right(90)
draw_spiral(L+5) # Recursive call, increasing length
draw_spiral(10) # Initial length
done()Running result:
The specific process of this example:
6. Advanced Recursion: Colorful Fractal Art
from random import randrange
from turtle import *
colormode(255)
color(0, 0, 0)
x = 0
ax = 20
hideturtle()
pensize(3)
tracer(5)
penup()
goto(0, 0)
pendown()
def a(l):
global x, ax
if l > 0:
x = x + ax
if x > 255:
ax = -20
x = 255
elif x < 0:
ax = 20
x = 0
color(255 - x, randrange(50, 200), randrange(50, 200))
for j in range(8):
for i in range(45):
forward(l / 4)
right(1)
a((l - 5) / 2) # Maintain original recursive parameter calculation
right(135)
for i in range(45):
forward(l / 4)
right(1)
right(135 + 45)
a(22)
done()Running result:
7. Precautions for Recursion
-
There must be a termination condition – Otherwise, it becomes a “dead loop of nesting”
-
Each recursion should reduce the problem size – For example, n→n-1
-
Be aware of call stack depth – Python’s default recursion depth is about 1000 layers
-
Important tool: Use
<span>sys.setrecursionlimit()</span>to adjust depth
Conclusion: The Power of Recursive Thinking
Recursion is not just a programming skill, but a way of thinking to decompose complex problems. Just like dismantling a Russian doll, breaking down a big problem into similar smaller problems and tackling them one by one. Mastering recursion will empower you with strong problem-solving abilities in fields like algorithms, AI, and graphics!
To understand recursion, you need to first understand recursion, then understand recursion… until you can understand recursion.