Pass-by-Value and Recursion

Two ideas complete your understanding of methods. First, how arguments are passed – "Is Java pass-by-value or pass-by-reference?" is asked in almost every Java interview, and most candidates get it slightly wrong. Second, recursion: a method solving a problem by calling itself on a smaller version of it.

Java is always pass-by-value

When you call a method, Java copies the value of each argument into the parameter. For primitives the value is the number itself, so the method can't affect the caller's variable:

public class Main {
    static void addBonus(int marks) {
        marks += 10;                      // changes the copy only
        System.out.println("inside: " + marks);
    }

    public static void main(String[] args) {
        int marks = 70;
        addBonus(marks);
        System.out.println("outside: " + marks);
    }
}

inside: 80
outside: 70

Objects: the reference is copied

For objects and arrays, the variable holds a reference. Java copies that reference – so the method gets a second reference to the same object. It can change the object's contents, but reassigning the parameter only changes its own copy.

import java.util.Arrays;

public class Main {
    static void addBonus(int[] marks) {
        marks[0] += 10;                   // changes the shared array
    }

    static void replace(int[] marks) {
        marks = new int[]{0, 0, 0};       // reassigns the local copy only
    }

    public static void main(String[] args) {
        int[] marks = {70, 80, 90};
        addBonus(marks);
        System.out.println(Arrays.toString(marks));
        replace(marks);
        System.out.println(Arrays.toString(marks));
    }
}

[80, 80, 90]
[80, 80, 90]

Recursion

A recursive method calls itself. Every correct recursive method has two parts:

• a base case that is answered directly and stops the recursion;
• a recursive case that calls the method on a smaller input, moving towards the base case.

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

    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(factorial(20));
    }
}

120
2432902008176640000

More recursive classics

public class Main {
    static int sumDigits(int n) {
        return n < 10 ? n : n % 10 + sumDigits(n / 10);
    }

    static boolean isPalindrome(String s, int i, int j) {
        if (i >= j) return true;
        return s.charAt(i) == s.charAt(j) && isPalindrome(s, i + 1, j - 1);
    }

    static long power(long base, int exp) {         // fast exponentiation
        if (exp == 0) return 1;
        long half = power(base, exp / 2);
        return exp % 2 == 0 ? half * half : half * half * base;
    }

    static int binarySearch(int[] a, int key, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = (lo + hi) >>> 1;
        if (a[mid] == key) return mid;
        return a[mid] < key ? binarySearch(a, key, mid + 1, hi) : binarySearch(a, key, lo, mid - 1);
    }

    public static void main(String[] args) {
        System.out.println(sumDigits(4096));
        System.out.println(isPalindrome("racecar", 0, 6));
        System.out.println(power(2, 40));
        System.out.println(binarySearch(new int[]{3, 8, 15, 23, 42, 57}, 42, 0, 5));
    }
}

19
true
1099511627776
4

The cost of recursion

Every call adds a stack frame. Without a base case – or with very deep input – the stack runs out:

public class Main {
    static int depth = 0;

    static void dive() {
        depth++;
        dive();                // no base case
    }

    public static void main(String[] args) {
        try {
            dive();
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError after many calls: " + (depth > 1000));
        }
    }
}

StackOverflowError after many calls: true

Recursion can also repeat work. Naive Fibonacci recalculates the same values exponentially many times; storing results (memoisation) or using a loop fixes it:

public class Main {
    static long[] memo = new long[91];

    static long fib(int n) {
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fib(10) + " " + fib(50) + " " + fib(90));
    }
}

55 12586269025 2880067194370816120

Practice

Summary

Interview practice: Core Java interview questions.