A "factorial" is a mathematical operation applied to a non-negative integer. It is represented by an exclamation mark (n!).

It is defined as the product (multiplication) of all positive integers less than or equal to n.

·         5! = 5 * 4 * 3 * 2 * 1 = 120

·         4! = 4 * 3 * 2 * 1 = 24

·         1! = 1

By special definition, the factorial of zero (0!) is 1. This is a very important rule that we will use later.

Factorial is a perfect example for programming because it can be solved in two very different ways: Iteration (loops) and Recursion.

This is the "bottom-up" approach. You start with a result of 1 and multiply it by 2, then 3, then 4, and so on, up to n.

Logic:

1.    Create a variable, result, and initialize it to 1.

2.    Create a for loop that starts a counter i at 1 (or 2) and goes up to n.

3.    Inside the loop, multiply: result = result * i;.

4.    After the loop finishes, result holds the final answer.

Example Code: Iteration

/*

 * Example: Finding Factorial using Iteration (a for loop).

 * This is the "bottom-up" method.

 */

#include <stdio.h>

// We use "long long" to store the result, as factorials

// get very large, very quickly. An "int" would overflow.

long long factorial_loop(int n);

int main() {

    int num = 5;

    printf("Iterative: %d! = %lld\n", num, factorial_loop(num));

    num = 10;

    printf("Iterative: %d! = %lld\n", num, factorial_loop(num));

    num = 0;

    printf("Iterative: %d! = %lld\n", num, factorial_loop(num));

    return 0;

}

long long factorial_loop(int n) {

    long long result = 1; // Start with 1

    // Handle the 0! = 1 case

    if (n == 0) {

        return 1;

    }

    // Loop from 1 up to n

    for (int i = 1; i <= n; i++) {

        result = result * i; // Build up the result

    }

    return result;

}

This method is very efficient. It is fast, uses very little memory (just for result and i), and is easy for most people to understand.

This is the "top-down" approach. It uses the mathematical definition of factorial, which is naturally recursive:

n! = n * (n-1)!

For example: 5! = 5 * 4!, 4! = 4 * 3!, and so on.

This "definition in terms of itself" is the key to recursion. To write this as a function, we need our two required parts:

1. The Recursive Step:

This is the general rule. We translate n! = n * (n-1)! directly into C code:

return n * factorial_recursive(n - 1);

2. The Base Case:

This is the "stop" condition. If we only had the rule above, factorial(3) would call factorial(2), then (1), then (0), then (-1)... forever. We need to stop.

The simplest problem we can solve directly is 0!. We know by definition that 0! = 1.

if (n == 0) { return 1; }

This stops the chain of calls and allows the solution to be "built" back up.

Example Code: Recursion

/*

 * Example: Finding Factorial using Recursion.

 * This is the "top-down" method.

 */

#include <stdio.h>

long long factorial_recursive(int n);

int main() {

    int num = 5;

    printf("Recursive: %d! = %lld\n", num, factorial_recursive(num));

    num = 0;

    printf("Recursive: %d! = %lld\n", num, factorial_recursive(num));

    return 0;

}

long long factorial_recursive(int n) {

    // 1. BASE CASE: The "stop" condition.

    if (n == 0) {

        return 1;

    }

    // 2. RECURSIVE STEP: The general rule.

    else {

        return n * factorial_recursive(n - 1);

    }

}

This is the part that can be confusing. The answer is the Call Stack. The computer uses a "stack" to keep track of all the function calls that are "paused," waiting for another function to finish.

Let's trace factorial_recursive(3):

1.    main() calls factorial(3).

o    The Call Stack has: [factorial(3)]

2.    factorial(3) starts. Is n == 0? No (n is 3).

o    It must go to the else block.

o    It needs to calculate: return 3 * factorial(2);

o    It can't return yet! It must "pause" and wait for factorial(2) to give it an answer.

3.    factorial(3) calls factorial(2).

o    The Call Stack now has: [factorial(3), factorial(2)]

4.    factorial(2) starts. Is n == 0? No (n is 2).

o    It must calculate: return 2 * factorial(1);

o    It also "pauses" and waits for factorial(1).

5.    factorial(2) calls factorial(1).

o    The Call Stack: [factorial(3), factorial(2), factorial(1)]

6.    factorial(1) starts. Is n == 0? No (n is 1).

o    It must calculate: return 1 * factorial(0);

o    It "pauses" and waits for factorial(0).

7.    factorial(1) calls factorial(0).

o    The Call Stack: [factorial(3), factorial(2), factorial(1), factorial(0)]

8.    factorial(0) starts. Is n == 0? YES!

o    It hits the BASE CASE.

o    It returns 1.

o    factorial(0) is finished and is popped off the stack.

9.    We're back in factorial(1), which was paused.

o    It just received the 1 from factorial(0).

o    It can now finish its calculation: return 1 * 1; (which is 1).

o    factorial(1) returns 1, is finished, and is popped off the stack.

10.             We're back in factorial(2), which was paused.

o    It just received the 1 from factorial(1).

o    It can now finish: return 2 * 1; (which is 2).

o    factorial(2) returns 2, is finished, and is popped off the stack.

11.             We're back in factorial(3), which was paused.

o    It just received the 2 from factorial(2).

o    It can now finish: return 3 * 2; (which is 6).

o    factorial(3) returns 6, is finished, and is popped off the stack.

12.             We're back in main(), which receives the final answer: 6.

Conclusion: The recursive version is more "elegant" and matches the mathematical definition, but it is slower and uses more memory (because of the Call Stack). For a simple problem like factorial, the iterative loop is a much better and more efficient solution.

We use factorial to *teach* recursion because it's the simplest way to see the "Base Case" and "Recursive Step" in action.