Thinking Recursively: Digits, Strings and Powers

The leap of faith

To write a recursive method, trust that it already works for smaller inputs. Then ask only: how do I use the smaller answer to build mine?

public class Main {
    // digitSum(4729) = 9 + digitSum(472)
    static int digitSum(int n) {
        if (n < 10) return n;
        return n % 10 + digitSum(n / 10);
    }

    // reverse("java") = reverse("ava") + 'j'
    static String reverse(String s) {
        if (s.length() <= 1) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(digitSum(4729));
        System.out.println(reverse("java"));
    }
}

Output

22
avaj

Fast power: halve the problem

2¹⁰ by multiplying ten 2s takes 10 steps. But 2¹⁰ = 2⁵ × 2⁵, and we only need to work out 2⁵ once. Halving each time makes it O(log n):

public class Main {
    static int calls = 0;

    static long power(long base, int exp) {
        calls++;
        if (exp == 0) return 1;
        long half = power(base, exp / 2);
        if (exp % 2 == 0) return half * half;
        return half * half * base;            // odd: one extra base
    }

    public static void main(String[] args) {
        System.out.println(power(2, 10) + " in " + calls + " calls");
        calls = 0;
        System.out.println(power(3, 39) + " in " + calls + " calls");
    }
}

Output

1024 in 5 calls
4052555153018976267 in 7 calls

Tip: Recursion that cuts the problem in half is O(log n). Recursion that removes just one item, like digitSum, is O(n) deep.