Understanding Recursion: Base Cases and Recursive Steps

Hello! In our last lesson, we built the merge helper function, the core component responsible for combining two sorted subarrays. We noted that to implement the full Merge Sort algorithm, we first need to master the "divide" part of the "divide and conquer" strategy. This division is achieved through a powerful programming technique.

This lesson will introduce you to that technique: recursion. We will explore how a function can call itself to solve a problem by breaking it down into smaller, more manageable pieces. By the end of our session, you will be able to define any recursive process by its two essential components: a base case and a recursive step. This is a fundamental concept in computer science that we will use to build the mergeSort function in our next lesson.

1. What is Recursion?

At its core, recursion is the process of a function calling itself. Imagine you have a set of Russian nesting dolls. To find the smallest doll, you open the largest one, which reveals a slightly smaller, identical-looking doll. You repeat this process—opening the current doll to find the next smaller one—until you reach the final, solid doll that cannot be opened.

This process has two key parts:

1. The recursive step: Opening a doll to find another, smaller doll inside. This is the repeated action.
2. The base case: Finding the smallest, solid doll. This is the condition that stops the process.

Without a base case, you would be opening dolls forever! In programming, this is called an infinite recursion, which usually causes your program to crash. Therefore, every useful recursive function must have a condition to stop calling itself.

Let's watch a short video that introduces this idea in C.

2. The Anatomy of a Recursive Function

Every recursive function is defined by two components:

1. Base Case: The simplest instance of the problem that can be solved directly, without making another recursive call. This is the stopping condition. A recursive function can have more than one base case.
2. Recursive Step (or Recursive Case): The part of the function that moves the problem closer to the base case. It breaks the problem into a smaller version of itself and calls the function with this smaller input.

The following video from Portfolio Courses offers an exceptionally clear definition of these two parts using a classic example: calculating a factorial.

The general structure of a recursive function in C often looks like this:

return_type recursive_function(parameters) {
    if (/* this is the base case */) {
        // Solve the simplest problem directly and return a value
        return simple_value;
    } else {
        // This is the recursive step
        // 1. Modify parameters to make the problem smaller
        // 2. Call the function again with the smaller problem
        return recursive_function(smaller_parameters);
    }
}

3. Example 1: Factorial

The factorial of a non-negative integer $n$, denoted as $n!$, is the product of all positive integers up to $n$. For example, $5!=5\times 4\times 3\times 2\times 1$.

We can define this recursively:

• Recursive Step: The factorial of any number $n$ is $n$ multiplied by the factorial of $(n-1)$. In math, $n!=n\times (n-1)!$.
• Base Case: The factorial of 1 (and 0) is 1. This stops the breakdown.

This image perfectly illustrates how calculating 6! is broken down recursively until it hits the base case, after which the results are combined back up.

Let's examine the C code for this, which implements this exact logic.

4. Example 2: Sum of Natural Numbers

Let's apply this pattern to another problem: calculating the sum of all natural numbers from 1 to $n$. For example, sum(4) = 4 + 3 + 2 + 1 = 10.

• Recursive Step: The sum of numbers up to $n$ is $n$ plus the sum of numbers up to $(n-1)$. That is, sum(n) = n + sum(n-1).
• Base Case: The sum of numbers up to 0 is 0. If we receive 0, we can stop and return 0 immediately.

The following image labels these two parts in a C function.

Now, let's watch a video that not only shows the code but also visualizes how the computer executes these recursive calls.

5. Hands-on Practice

Reading about recursion is one thing, but seeing it in action solidifies the concept. Here is the factorial function we discussed. Your task is to compile and run it, and then modify it to trace its own execution.

#include <stdio.h>

// Recursive function to calculate the factorial of a number
long long int factorial(int n) {
    // Add a printf here to see when the function is entered
    printf("Entering factorial with n = %d\n", n);

    long long int result;

    // Base case
    if (n == 0 || n == 1) {
        result = 1;
    }
    // Recursive case
    else {
        result = n * factorial(n - 1);
    }
    
    // Add a printf here to see what is being returned
    printf("Leaving factorial with n = %d, returning %lld\n", n, result);
    return result;
}

int main() {
    int num = 5;
    printf("Calculating factorial of %d...\n\n", num);
    
    long long int fact = factorial(num);
    
    printf("\nFinal result: Factorial of %d is %lld\n", num, fact);
    
    return 0;
}

Your Task:

1. Copy, compile, and run the code above.
2. Observe the output. Notice the "Entering..." messages stack up before any "Leaving..." messages appear. This shows the series of recursive calls.
3. Trace the output by hand and compare it to the "Factorial Recursion Diagram" from earlier. You should see the same pattern of calls and returns.

This exercise gives you a practical feel for the program's flow and the role of the call stack in managing the state of each recursive call.

Conclusion

In this lesson, we demystified the concept of recursion. You learned that it is a powerful technique where a function calls itself to solve a problem by repeatedly breaking it down into smaller pieces.

Key Takeaways:

• Recursion is a process where a function calls itself.
• Every recursive function must have a base case, which is a stopping condition that can be solved without further recursion.
• The recursive step is the part of the function that simplifies the problem and makes the recursive call with a smaller version of it.
• Problems like calculating factorials or summing a series of numbers can be defined elegantly using this structure.

Preview of the Next Lesson:
We are now ready to complete our implementation of Merge Sort. In the next lesson, we will write the mergeSort function itself. You will see how it uses recursion to repeatedly divide the array in half until it reaches the base case (subarrays of size 1), and then uses the merge function we wrote previously to combine them back into a fully sorted array.