Factorial

Q: What is the time complexity of computing a factorial?

Both the loop and the recursion do one multiplication for each number up to n , so the time is O(n) . The loop needs O(1) extra space. The recursion keeps one stack frame per call until the base case returns, so it uses O(n) space.

Q: Why is 0! equal to 1?

0! is the product of no numbers, and a product with no factors is 1 , the same way a sum with no terms is 0 . It also keeps the rule n! = n × (n-1)! true at n = 1 : 1! = 1 × 0! = 1 . Counting agrees: there is exactly one way to arrange zero items.

Q: Is recursion or a loop better for factorial?

They do the same multiplications and return the same answer. The recursive version reads like the mathematical definition, which is why it is a classic first exercise in recursion. The loop uses constant memory and cannot overflow the call stack, so it is the better choice in real code.

Q: What is the largest factorial that fits in an integer?

12! = 479001600 is the largest factorial that fits in a signed 32-bit integer. 20! = 2432902008176640000 is the largest for a signed 64-bit integer. Beyond that you need numbers of unlimited size, such as Python's int , Java's BigInteger or JavaScript's BigInt .

BeginnerMath and simulation Recursion

+10

The factorial of a whole number n, written n!, is the product of every whole number from 1 up to n. For example, 4! = 1 × 2 × 3 × 4 = 24. By definition 0! = 1. Your function gets n and returns n!.

Function

factorial(n: integer) → integer

ninteger: the whole number whose factorial you compute
Returnsinteger: the product of every whole number from 1 to n, which is 1 when n is 0

Constraints

0 ≤ n ≤ 12
The answer fits in a signed 32-bit integer: the largest one is 12! = 479001600.

Examples

Input: n = 5
Output: 120
Explanation: Multiply 1 × 2 × 3 × 4 × 5. The running product goes 1, 2, 6, 24 and ends at 120.

Input: n = 0
Output: 1
Explanation: There is nothing to multiply, and a product with no factors is 1. That is why 0! = 1.

+11 hidden tests on Submit

Follow-up

100! has 158 digits. Can you count how many zeros it ends with without computing it?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The factorial has two equivalent descriptions, and each one turns into code. As a product, n! = 1 × 2 × ... × n, which is a loop. As a recursive definition, 0! = 1 and n! = n × (n-1)!, which is a function that calls itself. Both do about n multiplications. The loop is the one to finish with, because it needs no call stack.

Recursion from the definition

Intuition

The factorial is defined through a smaller factorial: n! = n × (n-1)!. If you already know 4! = 24, then 5! = 5 × 24 = 120. A recursive function writes that sentence as code. To get factorial(n), it asks for factorial(n-1) and multiplies the answer by n.

The calls need a place to stop, the base case: factorial(0) returns 1 without calling anything. Each call lowers n by one, so from 5 the calls go 5, 4, 3, 2, 1, 0. Then the answers come back up the chain: 1, 1, 2, 6, 24, 120.

There are n + 1 calls and n multiplications, so the time is O(n). Every call waits on the stack until the call below it returns, so the stack holds n + 1 frames, which is O(n) space. With n ≤ 12 that is tiny, but the same pattern on a large input overflows the stack.

Algorithm

If n is 0, return 1. This is the base case.
Otherwise call the function on n-1.
Multiply that result by n and return it.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

Multiply in a loop

Intuition

Unroll the recursion and you get a running product. Start with result = 1 and multiply it by 2, then by 3, and so on up to n. For n = 5 the result goes 1, 2, 6, 24, 120.

Starting at 1 covers the smallest inputs too. For n = 0 and n = 1 the loop from 2 to n runs zero times, and the function returns the starting value 1, which is the right answer for both.

The loop does n-1 multiplications, O(n) time, and keeps one number, O(1) space. There is no call stack to overflow, which is why interviewers expect this version once you have shown the recursive one.

Algorithm

Set result = 1.
Loop k from 2 to n, both included.
Multiply result by k on every step.
Return result.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Pitfalls and edge cases

Factorial code is short, so the bugs sit at the edges.

Starting the product at 0. Every multiplication keeps it at 0. The starting value of a product is 1.
Stopping the recursion at n == 1 only. Called with 0, that function never reaches its base case: it goes on to -1, -2 and so on until the stack overflows. Make n == 0 the base case.
Looping with k < n instead of k ≤ n. That leaves out the last factor and returns (n-1)!, so 5 gives 24 instead of 120.
Ignoring overflow. 13! = 6227020800 does not fit in a signed 32-bit integer. In Java and C# the product silently wraps to a wrong number, in C signed overflow is undefined behavior, and a Rust debug build panics. A 64-bit integer holds up to 20!; past that you need big integers.
In Swift, writing for k in 2...n. A closed range whose end is below its start crashes at run time when n is 0 or 1.

Frequently asked questions4

What is the time complexity of computing a factorial?

Both the loop and the recursion do one multiplication for each number up to n, so the time is O(n). The loop needs O(1) extra space. The recursion keeps one stack frame per call until the base case returns, so it uses O(n) space.

Why is 0! equal to 1?

0! is the product of no numbers, and a product with no factors is 1, the same way a sum with no terms is 0. It also keeps the rule n! = n × (n-1)! true at n = 1: 1! = 1 × 0! = 1. Counting agrees: there is exactly one way to arrange zero items.

Is recursion or a loop better for factorial?

They do the same multiplications and return the same answer. The recursive version reads like the mathematical definition, which is why it is a classic first exercise in recursion. The loop uses constant memory and cannot overflow the call stack, so it is the better choice in real code.

What is the largest factorial that fits in an integer?

12! = 479001600 is the largest factorial that fits in a signed 32-bit integer. 20! = 2432902008176640000 is the largest for a signed 64-bit integer. Beyond that you need numbers of unlimited size, such as Python's int, Java's BigInteger or JavaScript's BigInt.