Recursion Explained: Mastering the Concept Step-by-Step

What is Recursion?

Recursion is a way of programming where a function calls itself to solve smaller parts of the same problem.

int fun() {
    printf("This function does not stop!!!.\n");
    fun(); // Recursive call without a base case
}

int main() {
    fun();
    return 0;
}

This is not a recursive program because a recursive program is expected to have a base case.

How does a base case function in recursion?

A base case helps stop the recursion in programs.

Example:-

int factorial(int n) {
    if(n == 0){
       return 1; // base case
    }
    return n * factorial(n - 1);
}

int main() {
    int n = 3;
    int result = factorial(n);
    printf("%d", result);
    return 0;
}

Output:
6

How does this program work? Step-by-step explanation:-

Step1:-

int factorial(3) {
    if(3 == 0){ // false
       return 1; // base case
    }
    return 3 * factorial(2); // 3 - 1 = 2 
}

int main() {
    int n = 3;
    int result = factorial(3); // n = 3
    println("%d", result);
    return 0;
}

Call the main function to the factorial function, passing a parameter n.

Step2:-

factorial(3) called to factorial(2)

int factorial(2) {
    if(2 == 0){ // false
       return 1; // base case
    }
    return 2 * factorial(1); // 2 - 1 = 1 
}

Step3:-

factorial(2) called to factorial(1)

int factorial(1) {
    if(1 == 0){ // false
       return 1; // base case
    }
    return 1 * factorial(0); // 1 - 1 = 0
}

Step4:-

factorial(1) called to factorial(0)

int factorial(0) {
    if(2 == 0){ // true
       return 1; // base case
    }
    return 0 * factorial(-1); // 0 - 1 = -1  *this line not executed*
}

Return values

factorial(0) = 1 // return 1 to factorial(1)
    |
factorial(1) = 1 * 1 = 1 // return 1 to factorial(2)
    |
factorial(2) = 2 * 1 = 2 // return 2 to factorial(3)
    |
factorial(3) = 3 * 2 = 6 // return 6 to result variable

// after print result