Java8使用lambda實(shí)現(xiàn)Java的尾遞歸

 /**
 * 階乘計(jì)算 -- 遞歸解決
 *
 * @param number 當(dāng)前階乘需要計(jì)算的數(shù)值
 * @return number!
 */
 public static int factorialRecursion(final int number) {
 if (number == 1) return number;
 else return number * factorialRecursion(number - 1);
 }

 /**
 * 階乘計(jì)算 -- 尾遞歸解決
 *
 * @param factorial 上一輪遞歸保存的值
 * @param number 當(dāng)前階乘需要計(jì)算的數(shù)值
 * @return number!
 */
 public static int factorialTailRecursion(final int factorial, final int number) {
 if (number == 1) return factorial;
 else return factorialTailRecursion(factorial * number, number - 1);
 }

/**
 * 尾遞歸函數(shù)接口
 * @author : martrix
 */
@FunctionalInterface
public interface TailRecursion<T> {
 /**
 * 用于遞歸棧幀之間的連接,惰性求值
 * @return 下一個(gè)遞歸棧幀
 */
 TailRecursion<T> apply();
 /**
 * 判斷當(dāng)前遞歸是否結(jié)束
 * @return 默認(rèn)為false,因?yàn)檎５倪f歸過程中都還未結(jié)束
 */
 default boolean isFinished(){
 return false;
 }
 /**
 * 獲得遞歸結(jié)果,只有在遞歸結(jié)束才能調(diào)用,這里默認(rèn)給出異常,通過工具類的重寫來(lái)獲得值
 * @return 遞歸最終結(jié)果
 */
 default T getResult() {
 throw new Error("遞歸還沒有結(jié)束,調(diào)用獲得結(jié)果異常!");
 }
 /**
 * 及早求值,執(zhí)行者一系列的遞歸,因?yàn)闂挥幸粋€(gè),所以使用findFirst獲得最終的棧幀,接著調(diào)用getResult方法獲得最終遞歸值
 * @return 及早求值,獲得最終遞歸結(jié)果
 */
 default T invoke() {
 return Stream.iterate(this, TailRecursion::apply)
  .filter(TailRecursion::isFinished)
  .findFirst()
  .get()
  .getResult();
 }
}

/**
 * 使用尾遞歸的類,目的是對(duì)外統(tǒng)一方法
 *
 * @author : Matrix
 */
public class TailInvoke {
 /**
 * 統(tǒng)一結(jié)構(gòu)的方法,獲得當(dāng)前遞歸的下一個(gè)遞歸
 *
 * @param nextFrame 下一個(gè)遞歸
 * @param <T> T
 * @return 下一個(gè)遞歸
 */
 public static <T> TailRecursion<T> call(final TailRecursion<T> nextFrame) {
 return nextFrame;
 }
 /**
 * 結(jié)束當(dāng)前遞歸，重寫對(duì)應(yīng)的默認(rèn)方法的值,完成狀態(tài)改為true,設(shè)置最終返回結(jié)果,設(shè)置非法遞歸調(diào)用
 *
 * @param value 最終遞歸值
 * @param <T> T
 * @return 一個(gè)isFinished狀態(tài)true的尾遞歸, 外部通過調(diào)用接口的invoke方法及早求值, 啟動(dòng)遞歸求值。
 */
 public static <T> TailRecursion<T> done(T value) {
 return new TailRecursion<T>() {
  @Override
  public TailRecursion<T> apply() {
  throw new Error("遞歸已經(jīng)結(jié)束,非法調(diào)用apply方法");
  }
  @Override
  public boolean isFinished() {
  return true;
  }
  @Override
  public T getResult() {
  return value;
  }
 };
 }
}

 /**
 * 階乘計(jì)算 -- 使用尾遞歸接口完成
 * @param factorial 當(dāng)前遞歸棧的結(jié)果值
 * @param number 下一個(gè)遞歸需要計(jì)算的值
 * @return 尾遞歸接口,調(diào)用invoke啟動(dòng)及早求值獲得結(jié)果
 */
 public static TailRecursion<Integer> factorialTailRecursion(final int factorial, final int number) {
 if (number == 1)
  return TailInvoke.done(factorial);
 else
  return TailInvoke.call(() -> factorialTailRecursion(factorial + number, number - 1));
 }

/**
 * 階乘計(jì)算 -- 尾遞歸解決
 *
 * @param factorial 上一輪遞歸保存的值
 * @param number 當(dāng)前階乘需要計(jì)算的數(shù)值
 * @return number!
 */
 public static int factorialTailRecursion(final int factorial, final int number) {
 if (number == 1) return factorial;
 else return factorialTailRecursion(factorial * number, number - 1);
 }

 @Test
 public void testRec() {
 System.out.println(factorialRecursion(100_000));
 }

java.lang.StackOverflowError
 at test.Factorial.factorialRecursion(Factorial.java:20)
 at test.Factorial.factorialRecursion(Factorial.java:20)
 at test.Factorial.factorialRecursion(Factorial.java:20)
 at test.Factorial.factorialRecursion(Factorial.java:20)
 at test.Factorial.factorialRecursion(Factorial.java:20)
Process finished with exit code -1

 public static TailRecursion<Long> factorialTailRecursion(final long factorial, final long number) {
 if (number == 1)
  return TailInvoke.done(factorial);
 else
  return TailInvoke.call(() -> factorialTailRecursion(factorial + number, number - 1));
 }

 @Test
 public void testTailRec() {
 System.out.println(factorialTailRecursion(1,10_000_000).invoke());
 }

50000005000000
Process finished with exit code 0

 public static long factorial(final long number) {
 return factorialTailRecursion(1, number).invoke();
 }

 @Test
 public void testTailRec() {
 System.out.println(factorial(10)); //結(jié)果為 3628800
 }