Start learning free

LESSON 256 OF 348 · RECURSION

Recursion in Kotlin: Writing a Recursive Factorial

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

    KOTLIN · RECURSION

    Recursion in Kotlin, explained

    What recursion is

    A function is recursive when it calls itself. The idea is to solve a problem by solving a smaller copy of the same problem and then using that answer to finish the original one. Recursion fits any problem that has this shape: factorials, searching a sorted array, walking through nested structures such as folders or trees, and many more.

    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 builds the answer from the result.

    Without a base case the calls never stop. Each call waits on the call stack for the next one to finish, so the stack grows until the program fails.

    The exercise: factorial

    The factorial of a non-negative integer n, written n!, is 1 * 2 * 3 * ... * n. The function factorial takes an Int n and returns n!. For n = 5 the result is 120, because 1 * 2 * 3 * 4 * 5 = 120.

    The statement allows O(n) time and O(n) extra space. The extra space is the call stack, which holds one pending call per level of recursion.

    The key observation is that n! = n * (n - 1)!. A factorial is just n times a smaller factorial. The smallest case is 0! = 1, and that is the base case.

    Step by step

    1. Write the base case. If n == 0, return 1. This is the input that can be answered directly, and it is also what stops the recursion.
    2. Write the recursive case. Return factorial(n - 1) * n. The argument n - 1 is smaller than n, so every call is closer to the base case.

    The solution in Kotlin

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

    Tracing the calls

    For factorial(3), the calls go down and the answers come back up:

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

    Nothing is multiplied until factorial(0) returns 1. After that the pending multiplications run from the inside out, as each call returns to the one that made it. At the deepest point there are n + 1 calls waiting at once, which is why the space is O(n). Each call does a constant amount of work, so the time is O(n).

    Kotlin details and gotchas

    • Return type is required. A function with a block body and no declared return type returns Unit. A recursive function should state its type, here : Int. For an expression body, Kotlin also requires the type when the function calls itself: fun factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1) is the same function written on one line.
    • Int overflows silently. An Int holds up to 2147483647, and 12! = 479001600 is the largest factorial that fits. factorial(13) returns 1932053504, which is not 13!, and factorial(20) returns -2102132736. No exception is thrown. With Long, the largest factorial that fits is 20! = 2432902008176640000; 21! wraps around to -4249290049419214848.
    • A missing base case or a wrong direction. factorial(-1) never reaches 0, because it calls factorial(-2), factorial(-3) and so on. Eventually the JVM throws StackOverflowError. The problem promises n >= 0, so the lesson doesn't guard for it.
    • Parentheses in the call. factorial(n - 1) subtracts first and passes the result. factorial(n) - 1 would call the function with the same n again and recurse forever.
    • Recursion versus a loop. A for loop computes the same product with O(1) extra space. This lesson uses recursion to practise the technique, and the other recursive problems in the chapter reuse the same two-part structure.

    Common mistakes

    • Returning 0 from the base case. Then every product ends up 0.
    • Writing the base case as n == 1 only. It works for n >= 1 but recurses until the stack overflows for n = 0, which the problem allows.
    • Forgetting return in front of the recursive call, so the value is computed and thrown away. The compiler reports that a function with a block body needs a return.

    Testing

    • factorial(0) gives 1.
    • factorial(1) gives 1.
    • factorial(5) gives 120.
    • factorial(12) gives 479001600.

    Key takeaways

    • A recursive function has a base case that answers directly and a recursive case that works on a smaller input.
    • Each call waits on the call stack, so recursion depth costs memory.
    • In Kotlin, an Int result overflows silently beyond 12!; use Long for larger inputs.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free