Introduction to Python Programming: Recursion

For programming beginners, “recursion” may sound like a complex and somewhat mysterious term in computer science. However, its core idea is actually evident in our daily lives.

This article will serve as a detailed “thinking guide” to introduce you to recursion in Python. We will use easy-to-understand analogies and structured code examples to help you grasp this powerful programming technique and learn how to use it.

1. Core Concept: What is Recursion?

In the field of programming, recursion refers to the process where a function calls itself directly or indirectly in its definition.

To understand this, let’s first look at an example outside of programming:

Imagine you are in line at a movie theater to buy a ticket, and you want to know your position in line. Instead of counting from the front, you ask the person in front of you, “What position are you?”

The person in front of you also wants to take a shortcut, so he/she asks the person in front of him/her, “What position are you?”

This process continues until it reaches the person at the front of the line. He/she knows they are in the 1st position, so he/she tells the person behind, “I am 1st.”

Then, the 2nd person knows they are behind the 1st person, so they are 2nd, and they tell the 3rd person.

This information is passed back layer by layer, and eventually, you get the answer from the person in front of you and can calculate your position.

In this example, the action of “asking the person in front what position they are” is a repetitive step. Each person in line is performing the same “inquiry” task until they encounter a known, simplest case (the person at the front of the line). Then, the answer is returned layer by layer.

This is the essence of recursion: breaking down a large problem into a smaller, similar subproblem until the problem is small enough to be solved directly.

2. Components of a Recursive Function

A correct and effective recursive function must contain two core parts, just as a product design blueprint must have key specifications.

2.1 Base Case

Base case, also known as the “termination condition,” is the “brake” that a recursive function must have. It is a scenario that can be solved directly and is the simplest problem case. When the function reaches this scenario, it stops calling itself and returns a definite result.

If there is no base case, the function will call itself indefinitely, eventually causing the program to crash due to resource exhaustion. This is like the previous example of the line; if there is no end to the line, the question will never reach a conclusion.

2.2 Recursive Step

Recursive step is the part of the function that “calls itself.” In this step, the function will “shrink” the current problem size a little and then pass this smaller problem to the next instance of itself to handle. It usually contains a return statement that calls the function itself but with parameters closer to the “base case.”

3. How to Assemble a Recursive Function: Using Factorial as an Example

Let’s practically assemble a recursive function using a classic mathematical problem—calculating the factorial.

The factorial of a positive integer n (written as n!) is the product of all positive integers less than or equal to n. For example:

• 5! = 5 * 4 * 3 * 2 * 1 = 120
• 3! = 3 * 2 * 1 = 6

Step 1: Find the Recursive Logic

Observing the calculation of factorial, we can find a pattern:

• 5! = 5 * 4!
• 4! = 4 * 3!
• 3! = 3 * 2!

This pattern can be summarized as:n! = n * (n-1)!. See, the problem of calculating n! has been broken down into calculating the smaller, similar problem of (n-1)!. This is the recursive step.

Step 2: Determine the Base Case

When does this decomposition process end? According to the mathematical definition, when n decreases to 1, the value of 1! is 1. We can also define the value of 0! as 1. This is the simplest case that we can solve directly. We can choose n=1 or n=0 as the base case.

Step 3: Write the Code

Now, we can translate the above analysis into Python code.

def factorial(n):
    """
    Calculate the factorial of a non-negative integer recursively.

    Parameters:
    n (int): A non-negative integer.

    Returns:
    int: The factorial value of n.
    """
    # 2.1 Base Case
    # When n is 0 or 1, the factorial result is 1, stop recursion.
    if n == 0 or n == 1:
        return 1
    # 2.2 Recursive Step
    # Otherwise, return n multiplied by the factorial of (n-1).
    else:
        return n * factorial(n - 1)

# --- Test our function ---
num = 5
print(f"{num} 的阶乘是: {factorial(num)}")

num = 3
print(f"{num} 的阶乘是: {factorial(num)}")

num = 1
print(f"{num} 的阶乘是: {factorial(num)}")

Execution Result:

5 的阶乘是: 120
3 的阶乘是: 6
1 的阶乘是: 1

Code Execution Process Analysis (Using factorial(3) as an example):

1. factorial(3) is called. 3 is not equal to 1, executing the else branch, it needs to calculate 3 * factorial(2).
2. To get the result, it calls factorial(2). 2 is not equal to 1, executing the else branch, it needs to calculate 2 * factorial(1).
3. To get the result, it calls factorial(1). 1 is equal to 1, triggering the base case, returning 1 directly.
4. factorial(2) gets the return value of factorial(1), which is 1, so it can complete the calculation of 2 * 1 and return the result 2.
5. factorial(3) gets the return value of factorial(2), which is 2, so it can complete the calculation of 3 * 2 and return the final result 6.

The whole process is like a journey of “going deeper” and then “returning,” where information is processed layer by layer on the return path.

4. “Safety Considerations”: Risks of Recursion

While recursion is elegant, there are two main risks to be aware of when using it:

4.1 Infinite Recursion

If your recursive function forgets to design a “base case” or the designed “base case” can never be reached, infinite recursion will occur. This will cause the function to call itself endlessly.

# Warning: This is an example that will cause an error
def infinite_recursion():
    # No base case, it will call itself forever
    return infinite_recursion()

# infinite_recursion() # Uncomment this line to run, the program will crash

4.2 Stack Overflow

When a function is called, the computer uses a memory area called the “call stack” to store information about each call (such as parameters, local variables, etc.). Each recursive call adds a layer to the stack. If the depth of recursion is too great (for example, calculating factorial(1000)), this memory may run out, leading to a "stack overflow" error.

Therefore, for problems with very deep recursion, using loops (iteration) is often a safer and more efficient choice than recursion.

5. Recursion vs. Looping (Iteration)

Any problem that can be solved with recursion can, in principle, also be solved with looping. They are two different ways of thinking about solving repetitive problems.

• Recursion: The code is usually more concise, closer to mathematical definitions and human decompositional thinking, and is more readable. However, it may have the risk of stack overflow, and the overhead of function calls is greater than that of loops.
• Looping (Iteration): The code is usually longer, but execution efficiency is higher, memory usage is more stable, and there is no limit on recursion depth.

For beginners, understanding the idea and structure of recursion is crucial. In practical programming, you can choose the most suitable method based on the nature of the problem and performance requirements.

Conclusion

Recursion is a powerful programming paradigm that simplifies complex problems into simpler problems of the same category. A qualified recursive function must contain a “base case” that allows it to stop and a “recursive step” that reduces the problem size.

While it is very elegant in code representation, one must also be cautious of the risks of infinite recursion and stack overflow. I hope this article helps you build a clear understanding of recursion and successfully apply it in your programming practice.