Recursion

Recursion in programming refers to the technique where a function calls itself to solve a smaller instance of the same problem. It is a powerful and elegant way to solve problems that can be broken down into smaller subproblems of the same type.

Recursive functions typically consist of two components:

Base Case: It defines the termination condition for the recursive function. When the base case is reached, the function stops calling and returns a specific value. This is necessary to prevent infinite recursion.
Recursive Case: It defines the logic for breaking down the problem into smaller subproblems and calling the function recursively with the reduced inputs. The recursive case allows the function to make progress toward the base case.

Let's try to calculate the factorial of a number using recursion.

Note

The factorial of a number n is defined as follows:
n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!

main


              1234567891011121314151617181920
            
#include <iostream>

// Function to calculate factorial
int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1) {
        std::cout << "Base Case: return 1" << std::endl;
        return 1;
    }

    // Recursive case: multiply n with factorial of (n-1)
    std::cout << "Recursive Case: " << n << " * factorial(" << n - 1 << ")" << std::endl;
    return n * factorial(n - 1);
}

int main()
{
    // Call the function
    std::cout << factorial(5) << std::endl;
}

Let's provide a step-by-step explanation of the code above:

Base Case: The base case is when the input n equals 0 or 1. In this case, the factorial is defined as 1. The base case ensures that the recursion terminates and prevents infinite recursion.

Recursive Case: The recursive case is the logic for calculating the factorial of n when n is greater than 1. It involves calling the factorial function recursively with n - 1 as the argument and multiplying it with n. This reduces the problem to a smaller subproblem by computing the factorial of a smaller number.

Call the function with argument equals 5. Here is step-by-step process:

factorial(5) calls factorial(4) and multiplies the result by 5.
factorial(4) calls factorial(3) and multiplies the result by 4.
factorial(3) calls factorial(2) and multiplies the result by 3.
factorial(2) calls factorial(1) and multiplies the result by 2.
factorial(1) is the base case and returns 1.
the multiplication continues back up the chain, resulting in the final factorial of 5 that equals 120.

Everything was clear?

Thanks for your feedback!

Section 4. Chapter 3