Introduction to Recursion in Python

Greetings, coder!

Today, we will recall the concept of recursion, as it will be useful throughout the course path. Recursion is a scenario in which a function calls itself. Recursion is valuable when you can break down a problem into smaller yet similar, simpler problems. It is critical in various tasks, such as sorting and searching algorithms.

The lesson for today involves understanding recursion, implementing it in Python, comparing it with iteration, and practicing debugging it.

Recursion in programming occurs when a function solves a problem by resolving smaller instances of the same problem. This is akin to peeling an onion — each layer is removed to reveal the next, similar layer underneath, until you reach the core. This layered peeling serves as a good metaphor for recursion.

However, it is paramount to define a proper base case in recursion to bring it to an end and avoid infinite loops.

Now, we will examine recursion in Python using factorials as an example. Here is a simple math fact about the factorial:

Using it, we can implement the factorial calculation recursively. Let's take a look.

Here is the Python implementation:

def factorial(n):
    # Base case:
    if n == 1:
        return 1
    # Recursive case:
    return n * factorial(n - 1)

In the implementation above, the function factorial() calls itself to compute the factorial of n. Here are the key things to pay attention to:

1. Base Case

   Within the factorial function, the base case is checked first. The base case is the condition under which the function stops calling itself. If n is 1, the function returns 1. This prevents infinite recursion and serves as the termination condition.

2. Recursive Case

   If n is not 1, the function proceeds to the recursive case. It returns n multiplied by the result of factorial(n - 1). This means the function calls itself with n reduced by 1, breaking down the problem into smaller subproblems until it reaches the base case.

Here is how we can call our recursive function:

def factorial(n):
    # Base case:
    if n == 1:
        return 1
    # Recursive case:
    return n * factorial(n - 1)

# The factorial of 5 is 120:
print("The factorial of 5 is:", factorial(5))

The result of factorial(5) is calculated as 5 * 4 * 3 * 2 * 1, which equals 120. In our program, it works in the following way:

1. We call the factorial(5), starting the recursion.
2. The result of the factorial(5) is 5 * factorial(4), according to the function's recursive case.
3. The result of the factorial(4) is 4 * factorial(3). Overall, the result of the function at this point is 5 * 4 * factorial(3).
4. Similarly, we get to 5 * 4 * 3 * 2 * factorial(1). The factorial(1) call triggers the base case and returns simply 1. Thus, the overall return value is 5 * 4 * 3 * 2 * 1, which is our correct answer.