Start learning free

LESSON 281 OF 415 · RECURSION

Recursion in Swift: The Factorial Function

Lesson O(n) Read the full explanation

In this video lesson we will learn about recursion, how recursive algorithms work and we will code a classic problem in recursive manner - Factorial:

Problem - Factorial:

Write a recursive function that given a non-negative integer n, returns the factorial of n, also denoted as n!

n! = 1 * 2 * 3 * ... * (n - 1) * n

Example:

Input: n = 5
Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 2
    Ctrl + Enter to check

    SWIFT · RECURSION

    Recursion in Swift, explained

    What recursion is

    A function is recursive when it calls itself. Each call solves a smaller version of the same problem, and a special small case is answered directly so the chain of calls can stop. Recursion suits problems that are defined in terms of themselves, like the factorial, trees, and many divide-and-conquer algorithms.

    Every recursive function has two parts:

    • a base case, an input small enough to answer without calling the function again;
    • a recursive case, which calls the function on a smaller input and uses the result to build the answer.

    Without a base case, the calls never stop: each one starts another until the program runs out of stack space and crashes.

    The exercise: factorial

    The factorial of a non-negative integer n, written n!, is the product 1 * 2 * 3 * ... * n. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120. By convention 0! is 1. The method factorial must compute it recursively. The statement asks for O(n) time and O(n) extra space.

    The definition already contains the recursion: n! equals n times (n - 1)!. So 5! is 5 * 4!, which is 5 * 4 * 3!, and so on until 0!, which is known to be 1.

    Step by step

    1. The base case. If n equals 0, return 1. This is where the chain of calls ends.
    2. The recursive case. Otherwise return factorial(n - 1) * n. Each call hands a smaller problem to the next one.

    The solution in Swift

    class Solution {
    func factorial(_ n: Int) -> Int {
        if n == 0 {
            return 1
        }
        return factorial(n - 1) * n
    }
}

    The Swift details worth a closer look:

    • Calling a method of the same class. Inside Solution, the method calls itself by plain name, factorial(n - 1). Because the parameter is declared with _, the call has no argument label.
    • The return type. The -> Int is required, and every path must return an Int. The if returns inside its braces and the last line returns the product, so the compiler is satisfied.
    • Overflow traps. Swift's Int is 64 bits. factorial(20) is 2432902008176640000 and fits, but 21! does not, and the multiplication stops the program with a run-time error instead of wrapping silently.

    How the calls unfold

    Calling factorial(3) produces this chain:

    factorial(3) = factorial(2) * 3
factorial(2) = factorial(1) * 2
factorial(1) = factorial(0) * 1
factorial(0) = 1

    The calls go down until the base case answers 1. Then each waiting call multiplies and returns: 1 * 1 = 1, then 1 * 2 = 2, then 2 * 3 = 6. Each pending call keeps its own copy of n on the call stack, so a call with argument n has n + 1 frames on the stack at its deepest point. That is the O(n) extra space in the statement, and the n + 1 calls are the O(n) time.

    Edge cases and common mistakes

    • Forgetting the base case. The calls never stop, and the program eventually crashes with a stack overflow.
    • A base case that is never reached. The statement guarantees a non-negative n. A negative argument would skip over 0 forever, with the same crash.
    • Wrong value for 0. Returning 0 for n == 0 makes every result 0. The empty product is 1.
    • Calling with the same argument. Writing factorial(n) inside factorial never makes the problem smaller.
    • Large inputs. A result above 20! does not fit in an Int and traps.

    Testing

    • n = 0 gives 1.
    • n = 1 gives 1.
    • n = 5 gives 120.
    • n = 20 gives 2432902008176640000.

    Key takeaways

    • A recursive function needs a base case and a recursive case that moves toward it.
    • The factorial follows from n! = n * (n - 1)! with 0! = 1.
    • Each pending call uses stack space, so the depth of the recursion is the extra space used.
    • Swift's Int overflow stops the program, so factorials beyond 20! need a different type.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free