/**
 * Diese Klasse wurde leicht angepasst (int -> long), damit man schön sehen kann,
 * dass eine endrekursive Funktion tatsächlich schneller ist als eine rekursive.
 * Die endrekursive Funktion ist bei mir im Schnitt 15-20x so schnell.
 * Die Schleife läuft bei mir noch schneller, was darauf hindeutet, dass der
 * Compiler, den ich bzw. meine IDE nutzt, die Endrekursion nicht ausreichend
 * optimiert. Das ist aber kein Indiz dafür, dass Tailrekursion schlechter ist
 * als Schleifen.
 * Noch ein Hinweis zu Endrekursion: Die "normale" Implementierung von
 * Fibonacci ist nicht endrekursiv! "Normal" bedeutet, dass man am Schluss
 * noch ZWEI rekursive Aufrufe hat (nämlich fib(n-1)+fib(n-2)). Da Diese
 * noch adiert werden müssen, wäre diese Implementierung nicht endrekursiv.
 * Es ließe sich aber endrekursiv umsetzen.
 */
public class TailRecursion {

    // x^y
    public static long pow(long x, int y) {
        return java.math.BigInteger.valueOf(x).pow(y).longValueExact();
    }

    // function f recursive
    public static long frec(long x) {
        return grec(x, 0);
    }

    // helper function g recursive
    public static long grec(long x, int pos) {
        if (x / 10 == 0) {
            return pow(x, pos);
        }
        return pow(x % 10, pos) + grec(x / 10, ++pos);
    }

    // function f tail recursive
    public static long ftailrec(long x) {
        return gtailrec(x, 0, 0);
    }

    // helper function g tail recursive (sum = Zwischenergebnis)
    public static long gtailrec(long x, int pos, long sum) {
        if (x / 10 == 0) {
            return sum + pow(x, pos);
        }
        return gtailrec(x / 10, pos + 1, sum + pow(x % 10, pos));
    }
    
    public static long floop(long x) {
        int pos = 0;
        long sum = 0;
        
        while (x / 10 != 0) {
            sum += pow(x % 10, pos++);
            x /= 10;
        }
        
        return sum + pow(x, pos);
    }

    // für die Zeitmessung
    public static long getTime() {
        return System.nanoTime();
    }

    public static void main(String[] args) {
        long timeRec, timeTailRec, timeLoop; // -> um den zeitlichen Unterschied zu sehen
        long resultRec, resultTailRec, resultLoop; // -> println braucht Zeit, die wir nicht messen wollen
        long n = Long.MAX_VALUE;
        
        timeRec = getTime();
        resultRec = frec(n);
        timeRec = getTime() - timeRec;
        
        timeTailRec = getTime();
        resultTailRec = ftailrec(n);  
        timeTailRec = getTime() - timeTailRec;
        
        timeLoop = getTime();
        resultLoop = floop(n);  
        timeLoop = getTime() - timeLoop;
        
        
        System.out.println("f recursive: " + resultRec + 
                           " (duration: " + timeRec + "ns)");
        System.out.println("f tailrec: " + resultTailRec + 
                           " (duration: " + timeTailRec + "ns)");
        System.out.println("f loop (iterative): " + resultLoop + 
                           " (duration: " + timeLoop + "ns)");
        System.out.println("\nTime difference between recursive and tail-recursive: " 
                    + (timeRec-timeTailRec) + "ns "
                    + "(speedup: x" + String.format("%.1f", 1.0*timeRec/timeTailRec) + ")");
    }
    
}