Start learning free

LESSON 255 OF 347 · RECURSION

Recursion in C#: Factorial and the Call Stack

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

    C# · RECURSION

    Recursion in C#, explained

    What recursion is

    A recursive method is a method that calls itself. Instead of solving a problem in one go, it solves a slightly smaller version of the same problem by calling itself, then uses that answer to finish the bigger one. Recursion fits problems that are made of smaller copies of themselves: a factorial, a folder tree, a number sequence defined by earlier terms.

    Every recursive method needs two parts:

    • A base case. A situation simple enough to answer directly, without another call. It is what stops the chain of calls.
    • A recursive case. A step that calls the method again on a smaller input, moving toward the base case.

    If the base case is missing, or the input never gets smaller, the method calls itself forever.

    The example: factorial

    The factorial of a non-negative integer n, written n!, is the product 1 * 2 * 3 * ... * n. So 5! = 120, and by convention 0! = 1.

    Factorial has a recursive shape. n! equals n times (n - 1)!, because the product up to n is the product up to n - 1 with one more factor. The chain ends at 0! = 1.

    The exercise, step by step

    The lesson asks for int Factorial(int n) inside class Solution.

    1. Write the base case. If n == 0, return 1. This is the case answered without a further call, and without it the recursion would never stop.
    2. Write the recursive case. Return Factorial(n - 1) * n. Each call hands the smaller problem n - 1 to the next one, and the multiplication happens once that answer comes back.
    class Solution {
    public int Factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return Factorial(n - 1) * n;
    }
}

    How the calls unfold

    Take Factorial(3). Nothing can be multiplied until the base case is reached, so the calls first go down, and then the answers come back up:

    Factorial(3) = Factorial(2) * 3
Factorial(2) = Factorial(1) * 2
Factorial(1) = Factorial(0) * 1
Factorial(0) = 1                  (base case)

Coming back up:
Factorial(1) = 1 * 1 = 1
Factorial(2) = 1 * 2 = 2
Factorial(3) = 2 * 3 = 6

    Each pending call waits in memory for its callee to return. C# keeps these waiting calls on the call stack, one frame per call, each holding that call's own n. For Factorial(n) there are n + 1 frames at the deepest point, so the time is O(n) and the extra space is O(n), matching the lesson's note.

    C# details and gotchas

    • Overflow wraps silently. int holds values up to 2,147,483,647. 12! is 479,001,600, which fits, but 13! is 6,227,020,800, which doesn't. In C#'s default unchecked arithmetic the result wraps around without an error, and Factorial(13) returns 1932053504, a wrong value. Using long pushes the limit to 20!.
    • No base case means a crash. Each call needs stack memory. If the recursion never ends, the stack runs out and .NET raises a StackOverflowException. This cannot be caught with try/catch, and it ends the program.
    • Negative input never reaches the base case. Factorial(-1) would call Factorial(-2), then Factorial(-3), and so on. The lesson promises a non-negative n, so the method doesn't guard against it.
    • The order of operands doesn't matter. n * Factorial(n - 1) is the same as Factorial(n - 1) * n. The call is evaluated either way before the multiplication.
    • Use PascalCase. The method is Factorial, not factorial. C# is case-sensitive, so a call to a lowercase name would not find it.
    • Return in every path. A C# method with a return type must return on every path. Here the if returns for the base case and the last line returns for the rest, so the compiler is satisfied.

    Writing recursion with confidence

    A reliable way to design a recursive method is to ask three questions in order:

    1. What is the smallest input, and what is its answer? That is the base case.
    2. If I trust that the method already works for a smaller input, how do I use that result to answer the current one? That is the recursive case.
    3. Does every recursive call move closer to the base case? If not, the method won't terminate.

    For factorial, the smallest input is 0 with answer 1. Trusting Factorial(n - 1), multiplying by n gives the answer for n. And n - 1 is closer to 0 than n.

    Factorial could also be written with a loop that multiplies a running product. Recursion earns its place on problems where the loop version is awkward, such as walking a tree or splitting a task in halves. The later lessons in this chapter use it that way.

    Key takeaways

    • A recursive method calls itself on a smaller input.
    • It needs a base case that stops the chain, and a recursive case that moves toward it.
    • Each pending call occupies a stack frame, so depth n costs O(n) space.
    • A missing base case ends in a StackOverflowException.
    • int overflow in C# is silent: Factorial(13) already gives a wrong answer, and long postpones it.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free