#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/recursion-fundamentals/factorial-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/recursion-fundamentals/factorial-implementation

Repovive

Factorial - Implementation - Recursion Fundamentals | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Factorial - Implementation

Writing the code

Here's the complete recursive factorial function:

function factorial(n)
    if n = 0 then
        return 1
    return n × factorial(n - 1)

Check the base case first: if $n = 0$ , return $1$ . Otherwise, you multiply $n$ by factorial(n - 1). For factorial(5), the function calls factorial(4), which calls factorial(3), down to factorial(0), which returns $1$ . Then the results multiply back up: $1 \times 1 \times 2 \times 3 \times 4 \times 5 = 120$ .

Time complexity: $O(n)$ since you make $n$ recursive calls. Space complexity: $O(n)$ due to the call stack depth.

Before moving on, try to trace factorial(3) yourself. How many function calls happen? What value does each one return? the call stack.