我是否应该在 java 中使用尾递归,即使它没有优化尾递归
Should I use tail recursion in java even if it does not optimize tail-recursion
网上看了下,发现java没有优化尾递归。
那么,如果头递归和尾递归会产生相同的结果,那么使用它有什么意义吗?
此外,循环的性能总是比递归好吗(tail和head)?因为有时不考虑迭代就更容易使用递归。
请告诉我是否应该使用循环。
刚开始接触递归,如有错误请指正
是的,java 中任何递归算法的性能几乎总是比使用循环重写相同的东西差得多。使用循环通常总是那么简单:
- 制作堆栈或双端队列对象。
- 制作一个代表所有相关状态的class。
- 编写一个循环,从堆栈或双端队列中获取内容并对其进行操作。
- 作为 'operating on it' 的一部分,您可以自由地从事新工作 - 类似于给自己打电话。
'formula' 应该适用于任何递归算法。
但是,您编写的绝大多数代码在性能方面都无关紧要。毫不夸张地说,如果您的应用程序对 CPU 有任何可衡量的影响,那么几乎总是您的应用程序正在使用的 CPU 资源的 99% 被您整个应用程序的 0.1% 用完了代码库。
然后的工作是 显然 [A] 发现 0.1% 和 [B] 使它更有效率。
剩下的99.9%就无所谓了。这不是 'death by a thousand cuts' 情况——这真的无关紧要。你可以编写比实际效率低 10 到 100 倍的代码,即使你犯了很多次这样的错误,只要它不在 0.1% 的关键路径中,你就永远不会注意到,也不会你的用户会。
因此,从这个意义上说,如果您认为使用递归更容易编写代码并且更易于阅读代码,那么请自重。只要知道如果你的探查器告诉你这个递归算法在那个 0.1%(关键路径),是的,第 1 步:重写远离递归。
旁注:只要您不递归太多,JVM 可以优化很多。某些 VM,如 azul,如果它是重复的(递归算法具有重复的堆栈跟踪),甚至会消除一堆堆栈跟踪。因此,即使 java 中的递归算法在性能方面也可以很好。可靠地获得此结果要困难得多,因为您现在依赖于自定义 VM 实现中所做的优化。
网上看了下,发现java没有优化尾递归。 那么,如果头递归和尾递归会产生相同的结果,那么使用它有什么意义吗?
此外,循环的性能总是比递归好吗(tail和head)?因为有时不考虑迭代就更容易使用递归。 请告诉我是否应该使用循环。
刚开始接触递归,如有错误请指正
是的,java 中任何递归算法的性能几乎总是比使用循环重写相同的东西差得多。使用循环通常总是那么简单:
- 制作堆栈或双端队列对象。
- 制作一个代表所有相关状态的class。
- 编写一个循环,从堆栈或双端队列中获取内容并对其进行操作。
- 作为 'operating on it' 的一部分,您可以自由地从事新工作 - 类似于给自己打电话。
'formula' 应该适用于任何递归算法。
但是,您编写的绝大多数代码在性能方面都无关紧要。毫不夸张地说,如果您的应用程序对 CPU 有任何可衡量的影响,那么几乎总是您的应用程序正在使用的 CPU 资源的 99% 被您整个应用程序的 0.1% 用完了代码库。
然后的工作是 显然 [A] 发现 0.1% 和 [B] 使它更有效率。
剩下的99.9%就无所谓了。这不是 'death by a thousand cuts' 情况——这真的无关紧要。你可以编写比实际效率低 10 到 100 倍的代码,即使你犯了很多次这样的错误,只要它不在 0.1% 的关键路径中,你就永远不会注意到,也不会你的用户会。
因此,从这个意义上说,如果您认为使用递归更容易编写代码并且更易于阅读代码,那么请自重。只要知道如果你的探查器告诉你这个递归算法在那个 0.1%(关键路径),是的,第 1 步:重写远离递归。
旁注:只要您不递归太多,JVM 可以优化很多。某些 VM,如 azul,如果它是重复的(递归算法具有重复的堆栈跟踪),甚至会消除一堆堆栈跟踪。因此,即使 java 中的递归算法在性能方面也可以很好。可靠地获得此结果要困难得多,因为您现在依赖于自定义 VM 实现中所做的优化。