Recursive strings and shapes

Recursive strings and self-similar problems. The classic recursion-into-reasoning problems:

• Reverse: rev(s) = rev(s.substring(1)) + s.charAt(0) with base length() <= 1. The append order is the entire difficulty — swapping it produces the input unchanged.
• Palindrome check with two indexes: isPal(s, lo, hi) — compare ends, recurse inward. Base: lo >= hi.
• Count structure: "how many ways" problems (climb 1-or-2 stairs) map to Fibonacci: ways(n) = ways(n-1) + ways(n-2), bases ways(0) = ways(1) = 1. Recognize the shape; do not simulate all paths.
• GCD: Euclid's gcd(a, b) = gcd(b, a % b), base b == 0. The exam loves it because it is progress-by-modulo.

Trace discipline: for strings, annotate each level with the substring it receives — level widths shrink visibly, which makes the base case obvious and wrong-index bugs visible.