18/19 Sem1 Q4

[fans2619]

Description

Hi, anyone can give me some idea on how to do this question? (Although I just found it was asked yesterday but there seems to be not many replies...) #515

Screenshots (if any):

[wei2912]

From what I understand, Java does not implement any form of Tail Call Optimisation currently (see https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all), so the solution would require the use of loops instead of recursion. This meets the requirements of the question, since the sum method can still be rewritten into a tail-recursive form.

The previous thread brought up a potential issue with the design of the classes:

If (n == 0), straightforward enough, we have a Base<Long>. However for the recursive case, we actually get a Recursive<Compute<Long>>

To address this, I would propose thinking of Compute<T> as a class that will perform a computation returning a T (perhaps specifying an abstract method compute that will return T), rather than a class that provides methods surrounding a Supplier<T>. So, Base<T> extends Compute<T> and Recursive<T> extends Compute<T>. The constructor of Base<T> takes in a supplier of the type Supplier<T>, while the constructor of Recursive<T> takes in a supplier of the type Supplier<Compute<T>>. For Base<T>, compute will simply retrieve the result from its supplier of type Supplier<T> and return that. On the other hand, for Recursive<T>, some sort of evaluation will need to be done through loops until a Base<T> is obtained.

I'll attach my answer below, but I would recommend trying to work through the logic above before looking at my code. Hope that helps!

---

abstract class Compute<T> {
    abstract T compute();
}

class Base<T> extends Compute<T> {
    private final Supplier<T> s;
    Base(Supplier<T> s) {
        this.s = s;
    }
    @Override
    T compute() {
        return this.s.get();
    }
}

class Recursive<T> extends Compute<T> {
    private final Supplier<Compute<T>> s;
    Recursive(Supplier<Compute<T>> s) {
        this.s = s;
    }
    @Override
    T compute() {
        Compute<T> c = this.s.get();
        while (c instanceof Recursive) {
            c = ((Recursive<T>) c).s.get();
        }
        return c.compute();
    }
}

[fans2619]

Thanks a lot for your explanation and solution @wei2912 !! It does help a lot. Just for reference, I also write the Main and test the code and it works well! Here is the Main4.java:

import java.util.Scanner;
public class Main4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long result = 0;
        result = sum(n, result).compute();
        System.out.println(result);
    }
    static Compute<Long> sum(long n, long s) {
        if (n == 0) {
            return new Base<>(() -> s);
        } else {
            return new Recursive<>(() -> sum(n - 1, n + s));
        }
    }
}