Simple Recursion in Practice

The topic of this lesson is Simple Recursion. As you may already know, recursion is a fundamental concept in computer science and an essential skill to master for any serious programmer. Using recursion can simplify code and make it easier to understand, although it can sometimes be hard to grasp. Basically, it is a method where the solution to a problem is based on solving smaller instances of the same problem.

Before diving deeper into this lesson, let's review the basics of recursion to ensure you have a solid foundation. Recursion is a process in which a function calls itself directly or indirectly. It's typically used to solve problems that can be broken down into smaller, more manageable sub-problems. The three key concepts of recursion are:

1. Base Case: This is the condition that stops the recursion. Without a base case, a recursive function would call itself indefinitely, leading to a stack overflow. The base case ensures that the recursion terminates at a certain point.

2. Recursive Case: This is where the function calls itself with a modified argument, moving towards the base case. It's the part of the function that breaks the problem into smaller sub-problems.

3. Call Stack: Each function call is placed on the call stack. When the base case is reached, the stack unwinds as each function call returns its result.

Let's quickly examine a factorial calculation, probably the most common and simple example of recursion. In math, the factorial of a number n is the product of all positive integers less than or equal to n. It sounds complicated, but if we think about it, the factorial of n can be calculated as the multiplication of n and the factorial of n - 1.

Our approach to the factorial function is:

1. Define the Function: Start by defining the factorial function that takes an integer n as input and returns an integer.

2. Base Case: Inside the function, check if n is equal to 0. If true, return 1. This serves as the base case that terminates the recursion.

3. Recursive Case: If n is not 0, return n multiplied by the result of calling factorial(n-1). This breaks down the problem by reducing n step by step towards the base case.

Here is how the solution will look:

#include <iostream>

int factorial(int n) {
    // Base case: factorial of 0 is 1
    if (n == 0) {
        return 1;
    }
    // Recursive case: multiply n by factorial of n-1
    else {
        return n * factorial(n-1);
    }
}

int main() {
    // Example usage
    std::cout << factorial(5) << std::endl;  // Outputs 120
    return 0;
}