Start learning free

LESSON 256 OF 348 · RECURSION

Recursion in TypeScript: The Factorial Example

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

    TYPESCRIPT · RECURSION

    Recursion in TypeScript, explained

    What recursion is

    A recursive function is a function that calls itself. It solves a problem by handing a smaller copy of the same problem to another call, and it uses the answer to build its own. Recursion fits problems that contain smaller versions of themselves: a factorial, a folder holding folders, a sorted list that can be cut in half.

    Every correct recursive function has two parts:

    • a base case, an input small enough to answer directly, without another call;
    • a recursive case, which calls the function on a smaller input and combines the result with the current one.

    If the base case is missing, or the inputs never get closer to it, the calls never stop.

    The factorial

    The factorial of a non-negative integer n, written n!, is 1 * 2 * 3 * ... * n. So 5! = 120. The definition hides a smaller copy of itself: n! = n * (n - 1)!. For example, 5! = 5 * 4!. The sequence has to end somewhere, and it does at 0! = 1, the base case. The exercise asks for a method factorial(n: number): number in the class Solution, with O(n) time and O(n) extra space.

    Step by step

    1. Write the base case. If n equals 0, return 1. The definition says 0! is 1, and this is the answer that needs no further call.
    2. Write the recursive case. Return this.factorial(n - 1) * n. Each call asks for the factorial of the next smaller number and multiplies the reply by its own n. The method belongs to a class, so the call goes through this.

    The solution in TypeScript

    class Solution {
    factorial(n: number): number {
        if (n === 0) {
            return 1;
        }
        return this.factorial(n - 1) * n;
    }
}

    What happens when it runs

    Calling factorial(3) starts a chain of calls. Each one waits for the next to finish:

    factorial(3) waits for factorial(2)
  factorial(2) waits for factorial(1)
    factorial(1) waits for factorial(0)
      factorial(0) returns 1
    factorial(1) returns 1 * 1 = 1
  factorial(2) returns 1 * 2 = 2
factorial(3) returns 2 * 3 = 6

    The calls pile up on the call stack until the base case answers, and then they finish one by one in the opposite order, each multiplying the value it receives. That is where the O(n) space comes from: at the deepest point, n + 1 calls are waiting. The time is O(n) too, because each call does one multiplication.

    TypeScript details and gotchas

    • === in the base case. n === 0 compares without converting types, and it is the usual habit. For a number the result is the same as with ==.
    • Types are erased. n: number is checked by the compiler only. When the program runs, nothing stops a caller from passing a string through a cast.
    • Bad inputs never reach the base case. factorial(-1) calls factorial(-2), then factorial(-3), and so on, never equal to 0. The same happens for factorial(2.5), which goes through 1.5, 0.5, -0.5 and past 0 without hitting it. In both cases Node stops with RangeError: Maximum call stack size exceeded. The lesson promises a non-negative integer, so the code doesn't guard against these.
    • Stack depth is limited. A deep enough recursion overflows the stack with that same RangeError. The limit is a few thousand to ten thousand calls depending on the environment, so very large n needs a loop.
    • A number is a double. Factorials grow fast. 170! is about 7.257e306, the largest factorial a number can hold, and factorial(171) returns Infinity. Integers beyond 2^53 are not guaranteed to be exact, so large results are only approximate. There is no integer overflow wrapping around as in some other languages.
    • Check the return type. The annotation : number makes the compiler complain if some path forgets to return a value.

    Common mistakes

    • Forgetting the base case. The calls never stop and the stack overflows.
    • Recursing on the same input. Calling this.factorial(n) instead of this.factorial(n - 1) is the same as no progress at all.
    • Dropping the multiplication. Returning only this.factorial(n - 1) gives 1 for every input, because the result of the recursion is never combined with n.
    • Leaving out this. Inside a class method, factorial(n - 1) by itself is not found, and the call fails.
    • Using base case 1 only. That works for n >= 1 but sends factorial(0) into an endless descent through negative numbers.

    Testing

    • factorial(0) gives 1.
    • factorial(1) gives 1.
    • factorial(5) gives 120.
    • factorial(10) gives 3628800.

    Key takeaways

    • A recursive function needs a base case and a recursive call on a smaller input.
    • Each pending call sits on the call stack, so a recursion of depth n uses O(n) space.
    • In TypeScript, call other methods of the class through this, and remember that a number is a double.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free