Start learning free

LESSON 250 OF 338 · RECURSION

Recursion in Go: 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

    GO · RECURSION

    Recursion in Go, explained

    What recursion is

    A function is recursive when it calls itself. It solves a problem by reducing it to a smaller version of the same problem, and keeps doing that until the problem is so small that the answer is known directly.

    Every recursive function has two parts:

    • the base case, an input for which the function returns an answer without calling itself;
    • the recursive case, which calls the function on a smaller input and uses that result to build the answer.

    Without a base case, or with a recursive case that doesn't move toward it, the calls never stop.

    The exercise: factorial

    The factorial of a non-negative integer n, written n!, is the product 1 * 2 * 3 * ... * n. For example 5! = 120. The function factorial(n int) int must compute it recursively, in O(n) time and O(n) extra space.

    The recursive idea is in the definition: n! = n * (n-1)!. If you know the factorial of the number below n, one multiplication gives the factorial of n. The chain ends at 0! = 1, which is the base case.

    Step by step

    1. Write the base case. If n == 0, return 1. Zero factorial is 1 by definition, and it gives every chain of calls a place to stop.
    2. Write the recursive case. Return factorial(n-1) * n. The call asks the same function for the next smaller factorial, and the product with n turns it into the answer for n.

    The solution in Go

    func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return factorial(n-1) * n
}

    How the calls unfold

    For factorial(3), each call waits for the next one:

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

    The base case returns 1. Then the waiting calls finish one after another, from the innermost out: factorial(1) is 1 * 1 = 1, factorial(2) is 1 * 2 = 2, and factorial(3) is 2 * 3 = 6. For factorial(5) the result is 120.

    Each unfinished call is kept on the call stack until the one below it returns, so a call for n uses n + 1 stack frames at its deepest. That is why the space cost is O(n), even though the function declares no slice or map. The time is O(n): one call and one multiplication per value from n down to 0.

    Go details

    • Calling itself needs no special syntax. A top-level function can refer to its own name, as factorial does inside its body.
    • Return types. The signature says the function returns an int, and both paths return one. Go rejects a function whose end can be reached without a return.
    • No tail-call optimisation. The Go compiler doesn't turn recursion into a loop, so each call really uses a new stack frame. Go stacks grow dynamically and can get very large, so ordinary depths such as a few thousand are fine, but there is a limit.
    • Integer overflow wraps silently. int is 64 bits here. factorial(20) is 2432902008176640000, which still fits, but factorial(21) overflows and gives -4249290049419214848, with no error. Use math/big for larger factorials.
    • Loop alternative. A for loop multiplying 1 by each number up to n gives the same result with O(1) space. The recursive version is the point of this lesson because the same pattern, a base case plus a smaller call, carries over to trees, backtracking and divide-and-conquer.

    Common mistakes

    • Missing base case. Without the n == 0 check, the calls go on through -1, -2 and so on and never return.
    • Not getting closer to the base case. Calling factorial(n) or factorial(n+1) from inside never reaches 0.
    • Negative input. The problem promises n >= 0. A negative n skips the base case forever, and the program eventually ends with a stack overflow, which is a fatal error in Go, not a panic that can be recovered.
    • Wrong base value. Returning 0 for n == 0 makes every result 0, since everything is multiplied by it. The base value must be 1, the neutral element of multiplication.
    • Forgetting to use the result. Calling factorial(n-1) and not multiplying it into the return value throws the work away.

    Key takeaways

    • Recursion solves a problem by solving a smaller copy of it, until a base case answers directly.
    • Always write the base case first, and make sure each call moves toward it.
    • Recursive calls wait on the call stack, so depth n means O(n) extra space.
    • Factorial grows fast: with a 64-bit int, results above 20! overflow.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free