Recursion is when a function calls itself with modified parameters. Each call works on a smaller, identical subproblem until a base case is reached. Base cases stop infinite loops and let the calls "unwind," combining results as the call stack returns.
Each recursive call waits for the next call to finish, creating a chain of pending operations. When the base case returns, the stack unwinds: each call resumes, performs its pending addition, and returns upward.
public class RecursionSums {
// Sum 1..n
static int sumToN(int n) {
if (n == 1) return 1; // base case
return n + sumToN(n - 1); // recursive call
}
// Sum of squares 1^2..n^2
static int sumSquares(int n) {
if (n == 1) return 1; // base case
return n * n + sumSquares(n - 1); // recursive call
}
}public class RecursiveBinarySearch {
static int bs(int[] a, int target, int lo, int hi) {
if (lo > hi) return -1; // base case (not found)
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid; // base case (found)
if (target < a[mid]) {
return bs(a, target, lo, mid - 1); // recursive call
} else {
return bs(a, target, mid + 1, hi); // recursive call
}
}
}