What recursion is, with your first function traced

2.1 What recursion actually is

A recursive function is a function that solves a problem by calling itself on a smaller version of the same problem, until the problem becomes so small that the answer is obvious.

Analogy — the cinema queue. You are standing in a long queue and want to know your position, but you can't see the front. So you tap the person ahead: "What's your position?" They don't know either, so they tap the person ahead of them. This repeats until it reaches the very first person, who says: "I'm position 1" — that's the base case, the question that needs no further asking. Now the answer flows backwards: each person takes the number they heard, adds 1, and passes it back. Eventually you hear a number, add 1, and you know your position.

That is recursion, completely: delegate a smaller version of the question forward; combine the answer on the way back.

Every correct recursive function has exactly two parts:

The #1 recursion bug: a missing base case, or a recursive call that doesn't actually shrink the problem. Either one means the calls never stop, the call stack fills up, and .NET throws StackOverflowException — which, unusually, cannot be caught in C#; it kills the process. Always write the base case first.

2.2 Your first recursive function, traced completely

Let's compute the sum 1 + 2 + ... + n. The recursive insight: the sum up to n is just n plus the sum up to n−1.

static int SumTo(int n)
{
    // BASE CASE: the smallest question, answered directly.
    if (n == 0)
        return 0;

    // RECURSIVE CASE: shrink the problem (n -> n-1),
    // trust the function to solve the smaller version,
    // then combine (+ n).
    return n + SumTo(n - 1);
}

Console.WriteLine(SumTo(4)); // 10