如何处理 Java 函数式编程中的非尾递归

在函数式编程中，尾递归是一种技巧，它允许函数调用自身而无需消耗额外的堆栈空间。然而，并非所有函数都可以以尾递归方式编写。

非尾递归的处理技巧

当无法将函数编写为尾递归时，有以下处理非尾递归的技巧：

立即学习“Java免费学习笔记（深入）”；

1. 循环

// 计算阶乘的非尾递归函数
public static long factorialImperative(int n) {
    long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

2. 线程

// 计算阶乘的非尾递归函数
public static long factorialTrampoline(int n) {
    // 通过线程为递归的每一步创建一个新的线程
    return new Thread(() -> {
        if (n == 0) {
            return 1L;
        } else {
            return n * factorialTrampoline(n - 1);
        }
    }).start().join();
}

3. 蹦床

// 定义一个辅助类来封装递归调用
public static class Trampoline<T> {

    private final Supplier<T> next;

    public Trampoline(Supplier<T> next) {
        this.next = next;
    }

    public static <T> Trampoline<T> done(T result) {
        return new Trampoline<>(() -> result);
    }

    public static <T> Trampoline<T> continueWith(Supplier<Trampoline<T>> next) {
        return new Trampoline<>(() -> next.get().next.get());
    }

    public T run() {
        return next.get();
    }
}

// 计算阶乘的非尾递归函数
public static long factorialTrampoline(int n) {
    return switch (n) {
        case 0 -> Trampoline.done(1L).run();
        default -> Trampoline
                .continueWith(() -> factorialTrampoline(n - 1))
                .continueWith(() -> Trampoline.done(n * next.get()))
                .run();
    };
}

实战案例：计算 Fibonacci 数列

// 使用循环计算 Fibonacci 数列
public static long fibonacciImperative(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        long previous = 0;
        long current = 1;
        for (int i = 2; i <= n; i++) {
            long temp = previous;
            previous = current;
            current = temp + current;
        }
        return current;
    }
}

// 使用蹦床计算 Fibonacci 数列
public static long fibonacciTrampoline(int n) {
    return Trampoline.<Long>done(0L)
            .continueWith(() -> fibonacciTrampoline(n - 1))
            .continueWith(() -> fibonacciTrampoline(n - 2))
            .continueWith(() -> Trampoline.done(next.get() + next.get()))
            .run();
}