Tracing a recursive method in Java/Kotlin

Tags: ,



In python, I can write a trace function like:

def trace(f):
    f.indent = 0
    def g(x):
        print('|  ' * f.indent + '|--', f.__name__, x)
        f.indent += 1
        value = f(x)
        print('|  ' * f.indent + '|--', 'return', repr(value))
        f.indent -= 1
        return value
    return g

fib = trace(fib)
print(fib(4))

and it’d print the recursive trace for any general recursive function beautifully:

$ python fib.py
|-- fib 4
|  |-- fib 3
|  |  |-- fib 2
|  |  |  |-- fib 1
|  |  |  |  |-- return 1
|  |  |  |-- fib 0
|  |  |  |  |-- return 1
|  |  |  |-- return 2
|  |  |-- fib 1
|  |  |  |-- return 1
|  |  |-- return 3
|  |-- fib 2
|  |  |-- fib 1
|  |  |  |-- return 1
|  |  |-- fib 0
|  |  |  |-- return 1
|  |  |-- return 2
|  |-- return 5
5

Is it possible to write a simple similar one in Java/Kotlin? Or is it only doable with AOP or the like?

Answer

EDIT: formatting does not 100% match yours, but that is easily fixable for you 🙂

Here is a code sample to accompany my comment. It is pretty ugly though but shows how its working. You can’t express it with a simple lambda as you cannot recurse lambdas in Java easily:

import java.util.function.BiFunction;
import java.util.function.Function;

class Scratch {
    private static int fib(int n, Function<Integer, Integer> _fib) {
        if (n <= 1)
            return n;
        return _fib.apply(n - 1) + _fib.apply(n - 2);
    }

    public static void main(String[] args) {
        Tracer<Integer, Integer> tracer = new Tracer<>(Scratch::fib);

        tracer.apply(5);
    }

    private static class Tracer<A, B> implements Function<A, B> {

        private final BiFunction<A, Function<A, B>, B> original;
        private int indent = 0;

        private Tracer(BiFunction<A, Function<A, B>, B> original) {
            this.original = original;
        }

        @Override
        public B apply(A a) {
            System.out.println("|  ".repeat(indent) + "|-- fib " + a);
            indent += 1;
            B result = original.apply(a, this);
            System.out.println("|  ".repeat(indent) + "|-- return " + result);
            indent -= 1;
            return result;
        }
    }
}

Output:

|-- fib 5
|  |-- fib 4
|  |  |-- fib 3
|  |  |  |-- fib 2
|  |  |  |  |-- fib 1
|  |  |  |  |  |-- return 1
|  |  |  |  |-- fib 0
|  |  |  |  |  |-- return 0
|  |  |  |  |-- return 1
|  |  |  |-- fib 1
|  |  |  |  |-- return 1
|  |  |  |-- return 2
|  |  |-- fib 2
|  |  |  |-- fib 1
|  |  |  |  |-- return 1
|  |  |  |-- fib 0
|  |  |  |  |-- return 0
|  |  |  |-- return 1
|  |  |-- return 3
|  |-- fib 3
|  |  |-- fib 2
|  |  |  |-- fib 1
|  |  |  |  |-- return 1
|  |  |  |-- fib 0
|  |  |  |  |-- return 0
|  |  |  |-- return 1
|  |  |-- fib 1
|  |  |  |-- return 1
|  |  |-- return 2
|  |-- return 5


Source: stackoverflow