Java中模拟尾调用递归的实现

秒速五厘米 2023-09-28 22:12 42阅读 0赞

> 这是一篇有技术含量的文章。

扫码关注《Java学研大本营》，加入读者群，分享更多精彩

![d2a9df0170148ae5566f4518a77e8748.png][]

从 Java 8 开始，Java 不提供尾调用优化 (TCO)。在研究它时，我了解到有一些安全原因导致团队放弃了 TCO，这导致递归代码的堆栈溢出，但可以使用函数式接口和 lambdas 来模拟它。

那么为什么要问 Lambda 呢？嗯，Lambda 是一项非常有趣的工作，因为你看，

lambda 不仅仅是`Functional Interfaces.`在编译类时匿名实现的语法糖，它会生成单个文件：`Lambda.class.`内部类没有额外的类文件。

Lambdas 是对象引用，它使用了一种叫做 invokedynamic 的东西:

public class Lambda {
        public static void main(String[] args){
            Engine start=()->
                 System.out.print("Do you know cats have 9 lives?");
            start.doSomeThing();
        }
    }
    interface Engine{
        void doSomeThing();
    }

现在让我们开始实现，让我们看看这个叫做四的幂的问题.

给定一个整数 n，`true`如果它是 4 的幂，则返回。否则，返回`false`。

整数`n`是 4 的幂，如果存在满足 的`x`整数`n == 4x`。

现在，如果我们使用普通递归来实现这个问题，它在 Java 8 中会看起来像这样:

class Solution {
        public boolean isPowerOfFour(int n) {
            Power<Long,Long> power=new Power<>();
            power.execute = (num,pow)->{
          
                if(pow==num){return true;}
                if(pow>num){return false;}
                return power.execute.execute(num,pow*4);
            };
    
            return power.execute.execute(n,1);
        }
    }
    @FunctionalInterface
    interface Execute{
        boolean execute(int num,int pow);
    }
    class Power<num,pow> {
        Execute execute;
    }

现在让我们运行代码 -> 我们遇到了我们的老朋友，或者我应该说敌人堆栈溢出

![12277094e9cac6d5d21e18955c468efb.png][]

现在让我们看看实现尾递归后的代码:

class Solution {
        public boolean isPowerOfFour(int n) {
           return new TailCallPower().power(n, 1).invoke();
        }
    }
    
    
    class TailCallPower{
        
        //Business Logic
        public static TailCall<Boolean> power(final long n, final long current) {
            if (current >= n){
                //Here insert the output to storage
                if(current==n){
                    return (new Storage()).done(true);
                }
                return (new Storage()).done(false);
            }
            else {
                return () -> power(n , current*4);
            }
        
       
        }
    }
    
    
    class Storage {
    
        public <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");
                }
            };
        }
    }
    
    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();
        }
    }

![c2161f75fad3938af77b45ffdf07e4a6.png][]

它被接受了，让我们看看实现细节

让我们一步一步来，这段代码在做什么

类 TailCallPower

我们将在这里编写我们的业务逻辑：这个类只是一个调用的包装器`() -> power(n , current*4);`，返回类型是 TailCall 接口所以你最后只是定义了我们的功能接口的定义，为了更好地理解请看下面的代码；

public class Engine {
    
        public static void main(String[] args){
            Add<Integer> add=(number1,number2)->{
                return number1+number2;
            };
            System.out.println(add.addition(2,3));
        }
    
    
    
    }
    @FunctionalInterface
    interface Add<T>{
        T addition(T a,T b);
    }

这可以重写为

public class Engine {
    
        public static void main(String[] args){
            System.out.println(addition().addition(3,2));
        }
        public static Add<Integer> addition(){
            return (num1,num2)->{
                return num1+num2;
            };
        }
    
    
    }
    @FunctionalInterface
    interface Add<T>{
        T addition(T a,T b);
    }

这可以重写为

public class Engine {
    
        public static void main(String[] args){
            System.out.println(addition().addition(3,2));
        }
        public static Add<Integer> addition(){
            return (num1,num2)->num1+num2;
        }
    
    
    }
    @FunctionalInterface
    interface Add<T>{
        T addition(T a,T b);
    }

所以这个想法是创建一个接口，其中递归发生在默认方法和业务逻辑中的另一个接口和一个包含两者的包装类

class Storage

顾名思义，在每个递归步骤中都会为我们的结果存储数据

因此，当程序完成时，您只需检索堆栈顶部的元素

等待蛋糕上的樱桃：该算法基于泛型，因此您可以根据需要在从阶乘到 fib 的任何地方实现它。

这是我实施的一些示例

在java中使用尾端递归的斐波那契示例

class Solution {
        public int fib(int n) {
             return Math.toIntExact(new TailCallPower().fib(n,0,1).invoke());
        }
    }
    
    
    
    class TailCallPower{
        
        //Business Logic
        public static TailCall<Long> fib(final long n,final long a,final long b) {
            if (n == 0) return (new Storage()).done(a);
            if (n == 1) return (new Storage()).done(b);
           
            
                return () ->  fib(n - 1, b, a + b); 
    
        
       
        }
    }
    
    
    class Storage {
    
        public <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");
                }
            };
        }
    }
    
    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();
        }
    }

爬楼梯

class Solution {
        public int climbStairs(int n) {
              if (n == 0) return 0;
              if(n==1){return 1;}
              if(n==2){return 2;}
              return Math.toIntExact(new TailCallPower().fib(n,2,3).invoke());
        }
    }
    
    
    
    class TailCallPower{
        
        //Bussiness Logic
        public static TailCall<Long> fib(final long n,final long a,final long b) {
         
            if (n == 3) return (new Storage()).done(b);
            
                return () ->  fib(n - 1, b, a + b); 
    
        
       
        }
    }
    
    
    class Storage {
    
        public <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");
                }
            };
        }
    }
    
    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();
        }
    }

![e5d9f8002b8ea443765dd6ef1a77f040.png][]

参考文章：

https://blog.knoldus.com/tail-recursion-in-java-8/ https://medium.com/@thakurganesh919/implementation-of-emulation-of-tail-call-recursion-in-java-a730cbdf40c2

### 推荐书单 ###

#### 1.《项目驱动零起点学Java》 ####

购买链接：https://item.jd.com/13607758.html

《项目驱动零起点学Java》贯穿6个完整项目，经过作者多年教学经验提炼而得，项目从小到大、从短到长，可以让读者在练习项目的过程中，快速掌握一系列知识点。

作者是国内知名Java教学者和传播者，一路披荆斩棘，兢兢业业20余年。积累了丰富的“培”“训”经验，也产出了很多优质的教学理论。

Java语言经过数十年的发展，体系逐渐变得庞大而复杂，本书芟繁就简，提炼出了最为重要的知识点，可以让读者轻松上手。本书配套有专栏课程，课程中提供了扩展内容。

《项目驱动零起点学Java》共分 13 章，围绕 6 个项目和 258 个代码示例，分别介绍了走进Java 的世界、变量与数据类型、运算符、流程控制、方法、数组、面向对象、异常、常用类、集合、I/O流、多线程、网络编程相关内容。《项目驱动零起点学Java》总结了马士兵老师从事Java培训十余年来经受了市场检验的教研成果，通过6 个项目以及每章的示例和习题，可以帮助读者快速掌握Java 编程的语法以及算法实现。扫描每章提供的二维码可观看相应章节内容的视频讲解。

![18d30c58271cf892105ba8afeebd8dde.png][]

#### 2.《Java编程讲义》 ####

购买链接：https://item.jd.com/13495830.html

《Java编程讲义》根据目前Java开发领域的实际需求，从初学者角度出发，详细讲解了Java技术的基础知识。

全书共15章，包括Java开发入门，Java语言基础，Java控制结构，数组，面向对象编程，继承和多态，抽象类、接口和内部类，异常处理，Java常用类库，集合与泛型，Lambda表达式，输入-输出流，多线程，JDBC数据库技术，网络编程等内容。内容全面覆盖．1ava开发必备的基础知识点，结合生活化案例展开讲解，程序代码给出了详细的注释，能够使初学者轻松领会Java技术精髓，快速掌握Java开发技能。

《Java编程讲义》适合作为高等院校相关专业的教材及教学参考书，也适合作为Java开发入门者的自学用书，还可供开发人员查阅、参考。

![f043a2b3b14ce77e2e57beb241571eac.jpeg][]

> > > > ### 精彩回顾 ###
> > 
> > [想要代码干净又整洁？这里有十大原则][Link 1]
> > 
> > [通过自学成为开发者的 9 种方法][9]
> > 
> > [怎么做一个有产品意识的软件工程师？][Link 2]

> > 扫码关注《Java学研大本营》，加入读者群，分享更多精彩

[d2a9df0170148ae5566f4518a77e8748.png]: https://img-blog.csdnimg.cn/img_convert/d2a9df0170148ae5566f4518a77e8748.png
[12277094e9cac6d5d21e18955c468efb.png]: https://img-blog.csdnimg.cn/img_convert/12277094e9cac6d5d21e18955c468efb.png
[c2161f75fad3938af77b45ffdf07e4a6.png]: https://img-blog.csdnimg.cn/img_convert/c2161f75fad3938af77b45ffdf07e4a6.png
[e5d9f8002b8ea443765dd6ef1a77f040.png]: https://img-blog.csdnimg.cn/img_convert/e5d9f8002b8ea443765dd6ef1a77f040.png
[18d30c58271cf892105ba8afeebd8dde.png]: https://img-blog.csdnimg.cn/img_convert/18d30c58271cf892105ba8afeebd8dde.png
[f043a2b3b14ce77e2e57beb241571eac.jpeg]: https://img-blog.csdnimg.cn/img_convert/f043a2b3b14ce77e2e57beb241571eac.jpeg
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247484467&idx=1&sn=a03c98cecf89bf808a36ea3a342c411a&chksm=c27a0be9f50d82ff7c33fc58d06ba1c3c40e4002f3ad2536cc6d23b0754cef741c0740ed1e5f#rd
[9]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247484737&idx=1&sn=65ecbefa3f5bc306763142d86b0caae1&chksm=c27a0a9bf50d838dbdc37210590e27edd029d9f563c377829367fa5bcd1374c44ed01196d339#rd
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzkzMDM3MjI3Nw==&mid=2247484703&idx=1&sn=b13abaffc02ff89c2c914ca3d1c289d6&chksm=c27a0ac5f50d83d368f7a7015b51c7eb4e463e8551c6c1dc7e4f0982cfb25f2407c9af8f6017#rd