L2 · Working engineerRecursion~3 min · 5 tests#48

Factorial Using Recursion

Q: What is the time complexity of Factorial Using Recursion in Python?

The optimal solution runs in O(n) time and O(n) auxiliary space. n multiplications, and n frames on the call stack until the base case returns.

Q: What is the brute-force approach, and how do you optimise it?

Recursion: O(n) time, O(n) space. n stack frames. Loop: O(n) time, O(1) space. Same multiplications, no stack.

Q: What follow-up questions do interviewers ask about Factorial Using Recursion?

Make it iterative. What happens at n = 5000?

Write factorial recursively with a correct base case, understand the O(n) call stack, and why Python's recursion limit matters. Live tests.

The problem

Return n! (n factorial) using recursion. 0! = 1.

Examples

Example 1
Input
```
factorial(5)
```
Expected output
```
120
```
Example 2
Input
```
factorial(0)
```
Expected output
```
1
```

+ 3 hidden tests on Submit.

Edge cases to ask about

n = 0
n = 1
Large n (recursion limit)

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · factorial

def factorial(n):
    """Return n! recursively."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Recursion	O(n)	O(n)	n stack frames.
bestLoop	O(n)	O(1)	Same multiplications, no stack.

Walkthrough of the optimal approach (try it yourself first)

Base case n <= 1 → 1; recursive case n * factorial(n - 1). Space is O(n) because each call waits on the stack for the next.

Python has a default recursion limit of about 1000 and no tail-call optimisation, so for large n the loop version (or math.factorial) is the production answer.

Complexity: O(n) time, O(n) space. n multiplications, and n frames on the call stack until the base case returns.

Reveal the reference solution

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Follow-ups interviewers ask

Make it iterative.
What happens at n = 5000?

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Factorial Using Recursion in Python?