Functions & Recursion

Functions let you break code into reusable pieces. In competitive programming, clean functions make your code readable, testable, and easier to debug. Recursion — a function calling itself — is the foundation of many powerful algorithms.

Function Mechanics & Variable Scope

int add(int a, int b) {
    return a + b;
}

int main() {
    int result = add(3, 4);  // result = 7
    return 0;
}

Scope

Variables have scope — they only exist within the block they're declared in:

int x = 10;  // global scope (avoid in competitive programming)

void foo() {
    int y = 20;  // local to foo
    // x is accessible here
}

void bar() {
    // y is NOT accessible here
    // x is accessible here
}

Local variables are created when a function is called and destroyed when it returns. Two functions can have variables with the same name — they're completely separate.

Return Values

A function returns control (and a value) to wherever it was called:

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Parameter Passing: Value vs. Reference

Pass by Value (default)

The function receives a copy of the argument. Changes inside the function don't affect the original:

void double_it(int x) {
    x *= 2;  // only modifies the local copy
}

int main() {
    int a = 5;
    double_it(a);
    // a is still 5
}

Pass by Reference

The function receives a reference to the original variable. Changes inside the function affect the caller:

void double_it(int &x) {
    x *= 2;  // modifies the original
}

int main() {
    int a = 5;
    double_it(a);
    // a is now 10
}

When to Use Each

• Pass by value: when the function only reads the argument (small types like int, char)
• Pass by reference (&): when the function needs to modify the argument, or to avoid copying large structures
• Pass by const reference (const &): when you want to read a large argument without copying, but don't need to modify it

// Efficient: no copy, can't modify
void print_vector(const vector<int> &v) {
    for (int x : v) cout << x << " ";
}

Recursion & the Call Stack

A recursive function calls itself with a smaller or simpler input:

int factorial(int n) {
    if (n <= 1) return 1;        // base case
    return n * factorial(n - 1); // recursive case
}

Every recursive function needs:

1. Base case: when to stop (no more recursive calls)
2. Recursive case: how to make progress toward the base case

The Call Stack

When you call a function, it's pushed onto the call stack. When it returns, it's popped off:

factorial(4)
  → 4 * factorial(3)
    → 3 * factorial(2)
      → 2 * factorial(1)
        → returns 1
      → returns 2 * 1 = 2
    → returns 3 * 2 = 6
  → returns 4 * 6 = 24

Why Recursion Matters

Many problems are naturally recursive: trees, divide-and-conquer, backtracking, and dynamic programming. Even if you could solve something iteratively, the recursive solution is often cleaner:

// Sum of array elements
int sum(int a[], int n) {
    if (n == 0) return 0;
    return a[n - 1] + sum(a, n - 1);
}

Recursion Pitfalls

• Stack overflow: too many recursive calls (depth > ~10⁵)
• Redundant work: same subproblem solved multiple times (use memoization)
• Missing base case: infinite recursion

Summary

• Functions encapsulate logic; local variables are scoped to the function
• Pass by value = copy; pass by reference (&) = modify original
• Use const & for large read-only parameters
• Recursion needs a base case and progress toward it
• Watch stack depth — ~10⁵ is the practical limit