Write a function to calculate the factorial of a number. Implement both recursive and iterative approaches. What is the maximum number for which factorial can be calculated in Dart?

Overview

Factorial (n!) is the product of all positive integers less than or equal to n. For example,

5! = 5 × 4 × 3 × 2 × 1 = 120

This classic problem demonstrates recursion, iteration, integer overflow handling, and Dart's BigInt for large numbers. It's frequently asked in interviews to test fundamental programming concepts.

Mathematical definition:

• textCopy

  n! = n × (n-1)!

  for n > 0
• textCopy

  0! = 1

  (by definition)

Approach 1: Iterative (Recommended)

Simple loop-based approach. Most efficient for production.

dartCopy
int factorial(int n) {
  if (n < 0) {
    throw ArgumentError('Factorial not defined for negative numbers');
  }

  int result = 1;

  for (int i = 2; i <= n; i++) {
    result *= i;
  }

  return result;
}

void main() {
  print(factorial(0));   // 1
  print(factorial(1));   // 1
  print(factorial(5));   // 120
  print(factorial(10));  // 3628800
  print(factorial(20));  // 2432902008176640000
}

Time Complexity: O(n) Space Complexity: O(1)

Pros:

• Simple and efficient
• No stack overflow risk
• Easy to understand

Approach 2: Recursive

Direct implementation of mathematical definition.

dartCopy
int factorialRecursive(int n) {
  if (n < 0) {
    throw ArgumentError('Factorial not defined for negative numbers');
  }

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

  // Recursive case
  return n * factorialRecursive(n - 1);
}

void main() {
  print(factorialRecursive(5));   // 120
  print(factorialRecursive(10));  // 3628800

  // ⚠️ Stack overflow for very large n (> 10000)
}

Time Complexity: O(n) Space Complexity: O(n) - recursion stack

Cons:

• Stack overflow risk for large n
• Higher memory usage
• Slower than iterative

Approach 3: Tail Recursion

Optimized recursive version (though Dart doesn't optimize tail calls).

dartCopy
int factorialTailRecursive(int n, [int accumulator = 1]) {
  if (n < 0) {
    throw ArgumentError('Factorial not defined for negative numbers');
  }

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

  return factorialTailRecursive(n - 1, n * accumulator);
}

void main() {
  print(factorialTailRecursive(5));   // 120
  print(factorialTailRecursive(10));  // 3628800
}

Note: Dart VM doesn't perform tail-call optimization, so this isn't faster than regular recursion.

Approach 4: Using BigInt (Large Numbers)

Handle factorials larger than standard int limit.

dartCopy
BigInt factorialBig(int n) {
  if (n < 0) {
    throw ArgumentError('Factorial not defined for negative numbers');
  }

  BigInt result = BigInt.one;

  for (int i = 2; i <= n; i++) {
    result *= BigInt.from(i);
  }

  return result;
}

void main() {
  print(factorialBig(20));   // 2432902008176640000
  print(factorialBig(50));   // 30414093201713378043612608166064768844377641568960512000000000000
  print(factorialBig(100));  // Huge number!

  // Standard int overflows at ~20-21
  // BigInt can handle arbitrarily large numbers
}

Time Complexity: O(n) Space Complexity: O(1) for variables, but result grows exponentially

Max with int (64-bit signed): ~20! (2,432,902,008,176,640,000) Max with BigInt: Limited only by memory

Approach 5: Memoization (Dynamic Programming)

Cache results for repeated calls.

dartCopy
class FactorialMemo {
  final Map<int, BigInt> _cache = {0: BigInt.one, 1: BigInt.one};

  BigInt calculate(int n) {
    if (n < 0) {
      throw ArgumentError('Factorial not defined for negative numbers');
    }

    if (_cache.containsKey(n)) {
      return _cache[n]!;
    }

    _cache[n] = BigInt.from(n) * calculate(n - 1);
    return _cache[n]!;
  }

  void clearCache() => _cache.clear();
}

void main() {
  var calc = FactorialMemo();

  print(calc.calculate(5));   // 120 (computed)
  print(calc.calculate(10));  // 3628800 (computed)
  print(calc.calculate(5));   // 120 (from cache)
  print(calc.calculate(8));   // Uses cached results up to 5
}

Use case: When calculating many factorials repeatedly.

Complete Solution Class

dartCopy
class Factorial {
  // Iterative (recommended)
  static int calculate(int n) {
    if (n < 0) throw ArgumentError('n must be >= 0');

    int result = 1;
    for (int i = 2; i <= n; i++) {
      result *= i;
    }
    return result;
  }

  // Recursive
  static int calculateRecursive(int n) {
    if (n < 0) throw ArgumentError('n must be >= 0');
    if (n <= 1) return 1;
    return n * calculateRecursive(n - 1);
  }

  // BigInt for large numbers
  static BigInt calculateBig(int n) {
    if (n < 0) throw ArgumentError('n must be >= 0');

    BigInt result = BigInt.one;
    for (int i = 2; i <= n; i++) {
      result *= BigInt.from(i);
    }
    return result;
  }

  // Check if result fits in int
  static bool fitsInInt(int n) {
    return n <= 20;  // 21! overflows 64-bit int
  }

  // Safe calculation (auto-use BigInt if needed)
  static dynamic calculateSafe(int n) {
    if (n < 0) throw ArgumentError('n must be >= 0');

    if (fitsInInt(n)) {
      return calculate(n);
    } else {
      return calculateBig(n);
    }
  }
}

void main() {
  print(Factorial.calculate(5));          // 120
  print(Factorial.calculateRecursive(5)); // 120
  print(Factorial.calculateBig(50));      // Very large number
  print(Factorial.fitsInInt(20));         // true
  print(Factorial.fitsInInt(21));         // false

  // Auto-select appropriate type
  print(Factorial.calculateSafe(10));     // int: 3628800
  print(Factorial.calculateSafe(25));     // BigInt: huge number
}

Comparison

Integer Limits in Dart

dartCopy
void demonstrateLimits() {
  // Standard int (64-bit signed)
  print('20! = ${factorial(20)}');  // OK
  // print(factorial(21));  // ❌ Overflow (negative or wrong value)

  // BigInt (unlimited)
  print('100! = ${factorialBig(100)}');  // ✅ Works!

  // Overflow example
  int overflow = 1;
  for (int i = 1; i <= 30; i++) {
    overflow *= i;
    print('$i! = $overflow');  // Watch it overflow after 20
  }
}

Dart int limits:

• Range: -2^63 to 2^63-1
• Max factorial without overflow: 20!
• Use BigInt for n > 20

Edge Cases

dartCopy
void testEdgeCases() {
  // Zero
  assert(factorial(0) == 1);

  // One
  assert(factorial(1) == 1);

  // Negative (should throw)
  try {
    factorial(-5);
    assert(false, 'Should have thrown');
  } catch (e) {
    assert(e is ArgumentError);
  }

  // Boundary (fits in int)
  assert(factorial(20) == 2432902008176640000);

  // Large number (use BigInt)
  assert(factorialBig(50).toString().length > 50);
}

Best Practices

1. Use Iterative for Production

dartCopy
// ✅ Recommended
int factorial(int n) {
  if (n < 0) throw ArgumentError('n must be >= 0');
  int result = 1;
  for (int i = 2; i <= n; i++) result *= i;
  return result;
}

2. Handle Negative Input

dartCopy
// ✅ Clear error message
if (n < 0) {
  throw ArgumentError('Factorial not defined for negative numbers');
}

3. Use BigInt for Large Numbers

dartCopy
// ✅ For n > 20
if (n > 20) {
  return calculateBig(n);
}

4. Document Limitations

dartCopy
/// Calculates n! using standard int.
///
/// Max value: 20! (larger values will overflow)
/// For n > 20, use [calculateBig] instead.
int factorial(int n) { ... }

Real-World Applications

1. Combinations & Permutations

dartCopy
int combinations(int n, int r) {
  return factorial(n) ~/ (factorial(r) * factorial(n - r));
}

print(combinations(5, 2));  // 10

2. Probability Calculations

dartCopy
double probability(int favorable, int total) {
  return factorial(favorable).toDouble() / factorial(total);
}

3. Mathematical Series

dartCopy
double exponential(double x, int terms) {
  double result = 0;
  for (int n = 0; n < terms; n++) {
    result += pow(x, n) / factorial(n);
  }
  return result;
}

Interview Tips

Common follow-ups:

1. "What about negative numbers?" → Undefined, throw ArgumentError

2. "What's the max factorial you can compute?" → 20! with int, unlimited with BigInt

3. "How to optimize for multiple calls?" → Use memoization/caching

4. "Iterative vs. recursive?" → Iterative is better (no stack overflow, less memory)

Resources

• BigInt Class - Dart API
• Factorial - Wikipedia
• Dart Numbers