Java8 Understanding tail-recursive function using a lambda expression:

Question

I am trying to lambda Java8 lambda expressions, Wherein I came across this example. I am unable to understand the program flow,

The the below example when the factorialTailRec(1, 5).invoke() statement is called the program flow is as shown below:

The program first goes to the factorialTailRec method and once and checks if the number value is equal to 1. In the first iteration, it's not so it goes to the else part.
In the else block the flow is redirected towards the call method inside the TailCall class which will return the same object.
Now the invoke method is called and then the Stream object tries to iterate through the result. I am not getting how the factorialTailRec is called again? They say its because of the below statement,
```
TailCall::apply
```

But, I am not understanding how that is happening.?

public class Factorial {
  

  public static TailCall<Integer> factorialTailRec(
    final int factorial, final int number) {      
    if (number == 1)
      return done(factorial);
    else
      return call(() -> factorialTailRec(factorial * number, number - 1));
  }

  public static int factorial(final int number) {
    return factorialTailRec(1, number).invoke();
  }

  public static void main(final String[] args) {
   
    System.out.println("//" + "START:FACTTAILREC_DISPLAY_5_OUTPUT");
    System.out.println(factorialTailRec(1, 5).invoke());
    System.out.println("//" + "END:FACTTAILREC_DISPLAY_5_OUTPUT");

   
  }
}


@FunctionalInterface
public interface TailCall<T> {
  
  TailCall<T> apply();
  
  default boolean isComplete() { return false; }
  //...

  default T result() { throw new Error("not implemented"); }
  
  default T invoke() {
    return Stream.iterate(this, TailCall::apply)
                 .filter(TailCall::isComplete)
                 .findFirst()
                 .get()
                 .result();
  }
}

public class TailCalls {
  public static <T> TailCall<T> call(final TailCall<T> nextCall) {
    return nextCall;
  }
  public static <T> TailCall<T> done(final T value) {
    return new TailCall<T>() {      
      @Override public boolean isComplete() { return true; }
      @Override public T result() { return value; }
      @Override public TailCall<T> apply() { 
        throw new Error("not implemented"); 
      }
    };
  }  
}

zhh · Accepted Answer · 2021-06-15 08:49:48Z

1

The below code

else
  return call(() -> factorialTailRec(factorial * number, number - 1));

is equivalent to

else {
  TailCall<Integer> nextCall = new TailCall<Integer>() {
    @Override
    public TailCall<Integer> apply() {
      return factorialTailRec(factorial * number, number - 1);
    }
  };
  return call(nextCall);
}

In the else block, a new TailCall object is created, with its apply function returning another TailCall object. (See FunctionalInterface)

A complete call chain would be: factorialTailRec(1, 5) -> factorialTailRec(5, 4) -> factorialTailRec(20, 3) -> factorialTailRec(60, 2) -> factorialTailRec(120, 1) -> done(120).

edited Jun 15, 2021 at 8:49

answered Jun 15, 2021 at 7:51

zhh

2,4161 gold badge14 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java8 Understanding tail-recursive function using a lambda expression:

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related