C++ Scope and Recursion

Scope decides where a variable's name can be used. Recursion is a function calling itself. They belong together: each recursive call gets its own local variables.

Local and block scope

A variable declared inside a function or block exists only inside it, from its declaration to the closing brace:

#include <iostream>

int main() {
    int total = 0;
    for (int i = 1; i <= 3; i++) {
        int square = i * i;     // only inside the loop
        total += square;
    }
    std::cout << "total " << total << "\n";   // i and square no longer exist
    return 0;
}

total 14

Global variables and static locals

A variable declared outside all functions is global: every function can use it. Globals make it hard to know who changed a value, so prefer parameters and return values. A static local variable keeps its value between calls while staying private to its function:

#include <iostream>

int nextId() {
    static int id = 0;   // created once
    return ++id;
}

int main() {
    std::cout << nextId() << " " << nextId() << " " << nextId() << "\n";
    return 0;
}

1 2 3

Recursion

A recursive function solves a problem by solving a smaller version of the same problem. It needs a base case that stops the calls and a recursive case that gets closer to it.

#include <iostream>

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

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

int main() {
    std::cout << "5! = " << factorial(5) << "\n";
    std::cout << "20! = " << factorial(20) << "\n";
    std::cout << "2^10 = " << power(2, 10) << "\n";
    return 0;
}

5! = 120
20! = 2432902008176640000
2^10 = 1024

long long is needed for 20!, which is far beyond the range of int.

Recursion on data

Recursion suits data with a recursive shape, such as text read from both ends:

#include <iostream>
#include <string>

bool isPalindrome(const std::string& s, int left, int right) {
    if (left >= right) return true;
    if (s[left] != s[right]) return false;
    return isPalindrome(s, left + 1, right - 1);
}

int main() {
    for (std::string w : {"level", "rotor", "coder"}) {
        std::cout << w << ": " << (isPalindrome(w, 0, static_cast<int>(w.size()) - 1) ? "yes" : "no") << "\n";
    }
    return 0;
}

level: intermediate
rotor: yes
coder: no

When recursion goes wrong

Each call waits on the call stack until the calls below it finish. Without a reachable base case, calls pile up until the stack is full and the program stops with a stack overflow. Very deep recursion (tens of thousands of levels) can overflow even when correct; a loop is then the better tool.

Practice exercises

1. Write a recursive function for the sum of the digits of a number.
2. Write a recursive Fibonacci function and print the first 15 numbers.
3. Write a recursive gcd(a, b): gcd(a, 0) = a, otherwise gcd(b, a % b).