Compute n! recursively, accounting for overflow
Implement Factorial(n) returning n! for n >= 0, with Factorial(0) == 1. Requirements: use recursion. The result type is long because the value grows fast — 20! already nears the long limit, so mention that checked arithmetic or a wider type guards against silent overflow.
public static long Factorial(int n)
{
// your code here
return 0;
}Write the implementation.
Recurse: the base case n <= 1 returns 1 (covers 0 and 1); otherwise return n * Factorial(n - 1). Cast to long so the product widens early. Because 21! overflows long, wrap the multiply in checked to throw rather than silently wrap. O(n) calls.
- ✗Returning
0in the base case instead of1, zeroing the whole product - ✗Computing in
intso the product overflows long beforelongwould - ✗Assuming
longcannot overflow —21!already does, silently withoutchecked
- →At what
ndoesFactorialoverflowlong, and how wouldBigIntegerchange that? - →How would you rewrite this iteratively to avoid deep recursion?
Task
Return n! recursively for n >= 0, with 0! = 1.
public static long Factorial(int n)
{
if (n <= 1) return 1; // base case: 0! = 1! = 1
return checked(n * Factorial(n - 1)); // checked catches overflow
}How it works
The recursion rests on the definition n! = n * (n-1)! with 0! = 1! = 1. The base case n <= 1 returns 1 — it stops the recursion and correctly covers both floors (0 and 1).
The result type is long because factorial grows very fast: 20! ≈ 2.4·10¹⁸ is already near the long limit, and 21! overflows it. The checked wrapper turns silent overflow into an OverflowException so the error does not pass unnoticed. For arbitrarily large n you need System.Numerics.BigInteger.
Recursion depth and the number of multiplications are linear, so the complexity is O(n).
