Factorial using Recursion

#include <iostream>
using namespace std;

// Recursive function to calculate factorial
int factorial(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // Recursive case
    return n * factorial(n - 1);
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    
    if (num < 0) {
        cout << "Factorial is not defined for negative numbers." << endl;
    } else {
        int result = factorial(num);
        cout << "Factorial of " << num << " = " << result << endl;
    }
    
    // Display factorial of first 10 numbers
    cout << "\nFactorials of 0-10:" << endl;
    for (int i = 0; i <= 10; i++) {
        cout << i << "! = " << factorial(i) << endl;
    }
    
    return 0;
}

Enter a number: 5
Factorial of 5 = 120

Factorials of 0-10:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

This program teaches you how to calculate Factorial using Recursion in C++. Recursion is a powerful programming technique where a function calls itself to solve a problem. Factorial is one of the classic examples of recursion, demonstrating how complex problems can be broken down into simpler subproblems.

---

1. What This Program Does

The program demonstrates recursive factorial calculation:

• Recursive function that calls itself
• Base case to stop recursion
• Recursive case that reduces problem
• Calculating factorial of numbers

Recursion provides elegant solution for factorial calculation.

---

2. Header Files Used

1. #include <iostream>
   • Provides cout and cin for input/output operations.

---

3. Understanding Recursion

Recursion Concept:

• Function calls itself
• Breaks problem into subproblems
• Base case stops recursion
• Recursive case reduces problem

Key Components:

• Base case: stops recursion
• Recursive case: calls itself
• Problem reduction: smaller subproblem
• Stack: stores function calls

---

4. Factorial Definition

Mathematical Definition:

• n! = n × (n-1) × (n-2) × ... × 2 × 1
• 0! = 1 (by definition)
• 1! = 1

Recursive Definition:

• n! = n × (n-1)!
• Base case: 0! = 1, 1! = 1
• Recursive case: n! = n × (n-1)!

---

5. Base Case

Stopping Condition:

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

How it works:

• Stops recursion
• Returns known value
• Prevents infinite recursion
• Essential for recursion

---

6. Recursive Case

Function Calls Itself:

return n * factorial(n - 1);

How it works:

• Calls factorial with smaller value
• Reduces problem size
• Multiplies result
• Builds solution from subproblems

---

7. Recursion Flow

Example: factorial(5):

1. factorial(5) calls factorial(4)
2. factorial(4) calls factorial(3)
3. factorial(3) calls factorial(2)
4. factorial(2) calls factorial(1)
5. factorial(1) returns 1 (base case)
6. Each level multiplies and returns
7. Result: 5 × 4 × 3 × 2 × 1 = 120

---

8. When to Use Recursion

Best For:

• Problems with recursive structure
• Tree/graph traversals
• Divide and conquer
• Mathematical definitions
• Natural recursive problems

Example Scenarios:

• Factorial, Fibonacci
• Tree traversals
• Sorting algorithms
• Backtracking
• Dynamic programming

---

9. Important Considerations

Base Case:

• Must be reachable
• Stops recursion
• Prevents infinite loops
• Essential component

Stack Overflow:

• Deep recursion uses stack
• Limited stack size
• May cause overflow
• Consider iterative for large n

Performance:

• Recursion has overhead
• Function call cost
• Stack frame creation
• Iterative may be faster

---

10. return 0;

This ends the program successfully.

---

Summary

• Recursion: function calls itself, breaks problem into subproblems.
• Factorial: n! = n × (n-1)!, base case: 0! = 1! = 1.
• Base case stops recursion, recursive case reduces problem size.
• Each recursive call creates stack frame, ensure base case reachable.
• Understanding recursion enables elegant problem-solving.
• Essential for recursive algorithms and divide-and-conquer approaches.

This program is fundamental for learning recursion, understanding recursive thinking, and preparing for advanced recursive algorithms in C++ programs.