Recursion

Functions That Call Themselves

Every recursive function needs a base case (stops recursion) and a recursive case (reduces toward base):

int factorial(int n) {
    if (n <= 1) return 1;           // base case
    return n * factorial(n - 1);   // recursive case
}
// factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

Fibonacci

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}
// 0,1,1,2,3,5,8,13,21...

Think recursively

Ask: "What is the simplest version of this problem?" That's your base case. Then: "How can I express the full problem in terms of a smaller version?" That's your recursive case.

Your Task

Implement gcd(int a, int b) — greatest common divisor — using the Euclidean algorithm:
gcd(a, 0) = a     gcd(a, b) = gcd(b, a % b)