Beginner recursion introduction

Recursion: functions that call themselves

A recursive function solves a problem by calling itself on a smaller version of the same problem. It's one of the biggest ideas in this course — graphs, trees, backtracking, and divide-and-conquer all lean on it.

The shape of every recursive function

Two ingredients, always:

A base case — the smallest input you can answer directly, no further recursion needed. This is what stops the function from calling itself forever.
A recursive case — shrink the problem, call yourself on the smaller version, and combine the result.

Sum the numbers from 1 to n:

function sumTo(n):
    if n == 0:            // base case
        return 0
    return n + sumTo(n-1)  // recursive case

sumTo(3) is 3 + sumTo(2) = 3 + 2 + sumTo(1) = 3 + 2 + 1 + sumTo(0) = 3 + 2 + 1 + 0 = 6.

How to think about it

Trust the recursion. Assume sumTo(n-1) already returns the right answer for n-1, then ask: how do I extend that to n? You don't need to trace the whole call tree in your head — just define one honest step and one stopping point, and let the machine do the rest.

Every recursion you write should make the input strictly smaller on the way to the base case. If it doesn't, it never stops. The next lesson looks at exactly how these calls stack up.