Explanation

• Concept: Recursion is a method where a function calls itself to solve smaller instances of the same problem.
• Process: The function calls itself with a reduced problem size until it reaches a base case that stops further recursion.
• Steps:
  • Define the base case(s) that terminate the recursion.
  • Define the recursive case, calling the function with a smaller input.
  • Combine the result of the recursive call with the current step's logic to form the final output.

Python Implementation

      
          def factorial(n):
    # Base case: factorial of 0 is 1
    if n == 0:
        return 1
    # Recursive case: n * factorial(n-1)
    return n * factorial(n - 1)

# Example usage:
print(factorial(5))  # Output: 120

        

Alternative Implementations

              def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# Example usage:
print(factorial_iterative(5))  # Output: 120

            

              from functools import lru_cache
@lru_cache(maxsize=None)          
def factorial_cached(n):
    if n == 0:
        return 1
    return n * factorial_cached(n - 1)

# Example usage:
print(factorial_cached(5))  # Output: 120

            

              def factorial_reduce(n):
    from functools import reduce
    from operator import mul
    return reduce(mul, range(1, n + 1), 1)

# Example usage:
print(factorial_reduce(5))  # Output: 120

            

              from functools import lru_cache, reduce
from operator import mul
from datetime import datetime

def factorial_recursive(n):
    """Basic recursive implementation."""
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

def factorial_iterative(n):
    """Iterative implementation - most efficient for large numbers."""
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

@lru_cache(maxsize=None)
def factorial_cached(n):
    """Cached recursive implementation - efficient for repeated calculations."""
    if n == 0:
        return 1
    return n * factorial_cached(n - 1)

def factorial_reduce(n):
    """Functional approach using reduce."""
    return reduce(mul, range(1, n + 1), 1)

def benchmark(n=20, iterations=1000):
    """Benchmark different implementations."""
    implementations = {
        'Recursive': factorial_recursive,
        'Iterative': factorial_iterative,
        'Cached': factorial_cached,
        'Reduce': factorial_reduce
    }
    
    results = {}
    for name, func in implementations.items():
        start = datetime.now()
        for _ in range(iterations):
            func(n)
        end = datetime.now()
        duration = (end - start).total_seconds()
        results[name] = duration
    
    return results

# Run benchmark
n = 20
iterations = 1000
print(f"Benchmarking factorial implementations with n={n}, iterations={iterations}:")
results = benchmark(n, iterations)

# Print results
for name, duration in results.items():
    print(f"{name:10} implementation took: {duration:.4f} seconds")

# Test correctness
test_n = 5
print(f"\nVerifying correctness with n={test_n}:")
results = {
    'Recursive': factorial_recursive(test_n),
    'Iterative': factorial_iterative(test_n),
    'Cached': factorial_cached(test_n),
    'Reduce': factorial_reduce(test_n)
}
for name, result in results.items():
    print(f"{name:10} result: {result}")

            

Usage and Applications