`
deepinmind
  • 浏览: 450819 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
1dc14e59-7bdf-33ab-841a-02d087aed982
Java函数式编程
浏览量:41552
社区版块
存档分类
最新评论

关于Java中尾递归的优化

阅读更多


最近总有人问我,Java SE8里有没有针对尾调用做优化(这是一种特殊的函数调用)。这个优化和递归调用密切相关,而递归调用对函数式语言来说尤其重要,因为它们通常都基于递归来进行设计编码。本文会介绍到什么是尾调用,怎样可以对它进行有效的优化,以及Java 8在这方面是如何做的。

在深入这个话题之前,我们先来了解下什么是尾调用。

什么是尾调用?

尾调用指的是一个方法或者函数的调用在另一个方法或者函数的最后一条指令中进行(为了简单,后面我就都称作函数调用了)。Andrew Koenig在他的博客中有关于这个话题的介绍。下面定义了一个foo()函数作为例子:

int foo(int a) {
  a = a + 1;
  return func(a);
}


func()函数的调用是foo()函数的最后一条语句,因此这是一个尾调用。如果在调用了func()之后,foo()函数还执行了别的指令才返回的话,那么func()就不再是一次尾调用了。

你可能在想这些语义有什么意义。如果尾调用不是一个递归的函数调用的话,这些概念确实不重要。比如:

int fact(int i, int acc) {
  if ( i == 0 ) 
    return acc;
  else
    return fact( i – 1, acc * i);
}

int factorial(int n) {
  if ( n == 0 )
    return 1;
  else
    return fact( n – 1, 1 );
}


下图中有fact()对应的汇编代码,就在C代码的右边。红色的箭头指向的是fact()函数的最后两条指令,一条是调用fact()自己,一个是return语句对应的MOV指令。这符合尾调用的定义。



尽管我用的是C代码来介绍这个,但其实在Java里也是一样的。事实上,你可以把这段代码拷贝到Java类里,它也能通过编译并正常工作。那么到底有什么可以优化的呢?

尾调用的优化

任何的尾调用,不只是尾递归,函数调用本身都可以被优化掉,变得跟goto操作一样。这就意味着,在函数调用前先把栈给设置好,调用完成后再恢复栈的这个操作(分别是prolog和epilog)可以被优化掉。比如说下面的这段代码:

int func_a(int data) {
  data = do_this(data);
  return do_that(data);
}


函数do_that()是一个尾调用。没有优化过的汇编代码看起来大概是这样的:


...     ! executing inside func_a()
push EIP    ! push current instruction pointer on stack
push data   ! push variable 'data' on the stack
jmp do_this ! call do_this() by jumping to its address
...     ! executing inside do_this()
push EIP    ! push current instruction pointer on stack
push data   ! push variable 'data' on the stack
jmp do_that ! call do_that() by jumping to its address
...     ! executing inside do_that()
pop data    ! prepare to return value of 'data'
pop EIP ! return to do_this()
pop data    ! prepare to return value of 'data'
pop EIP ! return to func_a()
pop data    ! prepare to return value of 'data'
pop EIP ! return to func_a() caller
...


注意到对于数据以及EIP寄存器(用来返回数据并且恢复指令指针),POP指令被连续执行了多次。可以通过一个简单的JMP指令将一组关联的epilog和prolog操作(将数据和EIP进行压栈)优化掉。这是因为do_that()函数会替func_a函数执行这段epilog代码。

这个优化是安全的,因为func_a函数在do_that()返回后就不再执行别的指令了。(注意:如果要对do_that()返回的值进行处理的话,就不能执行这个优化,因为do_that()就不再是一个尾调用了)。

下面是尾调用优化后的结果:

...     ! executing inside func_a()
push EIP    ! push current instruction pointer on stack
push data   ! push variable 'data' on the stack
jmp do_this ! call do_this() by jumping to its address
...     ! executing inside do_this()
push EIP    ! push current instruction pointer on stack
push data   ! push variable 'data' on the stack
jmp do_that ! call do_that() by jumping to its address
...     ! executing inside do_that()
pop data    ! prepare to return value of 'data'
pop EIP ! return to do_this()
pop data    ! prepare to return value of 'data'
pop EIP ! return to func_a() caller
pop data    ! prepare to return value of 'data'
pop EIP ! return to func_a() caller...


看起来稍微有点不同,这是优化前的代码:

   
int func_a(int data) {
data = do_this(data);push EIP ! prolog<br>push data ! prolog<br>jmp do_this ! call<br>...<br>pop data ! epilog<br>pop EIP ! epilog
return do_that(data);push EIP ! prolog<br>push data ! prolog<br>jmp do_that! call<br>...<br>pop data ! epilog<br>pop EIP ! epilog
}pop data ! epilog<br>pop EIP ! epilog


这是优化后的:

   
int func_a(int data) {
data = do_this(data);push EIP ! prolog<br>push data ! prolog<br>jmp do_this ! call<br>...<br>pop data ! epilog<br>pop EIP ! epilog
return do_that(data);jmp do_that ! goto...
}pop data ! epilogpop EIP ! epilog


比较一下第三行,你就可以看到节省了多少行机器代码。当然光这个而言并不能代表这个优化的真正价值。如果和递归结合到一起的话,这个优化的价值就显现出来了。

如果你再看下上面的那个递归的阶乘函数,你会发现如果使用了这个优化的话,所有原来不断重复的prolog和epilog汇编代码现在都消失了。最终把下面的递归伪代码:

call factorial(3)
  call fact(3,1)
    call fact(2,3)
      call fact(1 6)
        call fact(0,6)
        return 6
      return 6
    return 6
  return 6
return 6


变成这个迭代式的伪代码:

call factorial(3)
  call fact(3,1)
  update variables with (2,3)
  update variables with (1,6)
  update variables with (0,6)
  return 6
return 6


也就是说,它用一个循环替换掉了递归,大多数C/C++,Java程序员也正是这么干的。这个优化不止是减少了大量的递归函数调用带来的prolog和epilog,它还极大的减轻了栈的压力。不作这个优化的话,计算一个很大的数的阶乘很可能会让栈溢出——也就是,用光了所有分配给栈的内存。把代码优化成循环后就消除了这个问题。由于函数式语言的开发人员经常使用递归,所以大多数函数式语言的解释器都会进行尾调用的优化。


Java是怎么做的?

正如我前面提到的,Java程序员一般都使用循环,而尽量不用递归。比如,下面是一个迭代式的阶乘的实现:

int factorial(int n) {
   int result = 1;
   for (int t=n; t > 1; t--)
       result *= t;
   return result;
 }


因此对大多数Java开发人员来说,Java不进行尾调用优化并不是什么大问题。不过我猜或许很多Java程序员都没有听说过尾调用优化这回事。不过当你在JVM上运行函数式语言的话,这就成为一个问题了。递归的代码在自己语言的解释器里运行得好好的,可能一到JVM上就突然把栈给用完了。

值得注意的是,这并不是JVM的BUG。这个优化对经常使用递归的函数式语言的开发人员来说非常有用。我最近经常和Oracle的Brian Goetz提到这个优化,他总是说这个在JVM的开发计划表上,不过这不是一个优先级特别高的事。就目前来说,你最好自己去做优化,当你使用函数式语言在JVM上进行开发的时候,尽管避免使用过深的递归调用。


原创文章转载请注明出处:http://it.deepinmind.com

英文原文链接 


6
3
分享到:
评论
2 楼 -之诸暇 2014-04-16  
fair_jm 写道
像scala有@tailrec 这样的注解来标明这个函数是尾递归要进行优化
尾递归好处多多啊 栈空间使用是一个常量 不用担心stackoverflow 执行效率也高~~

嗯,现在是得靠各个语言自己的编译器去优化了。有优化过的一般没问题
1 楼 fair_jm 2014-04-16  
像scala有@tailrec 这样的注解来标明这个函数是尾递归要进行优化
尾递归好处多多啊 栈空间使用是一个常量 不用担心stackoverflow 执行效率也高~~

相关推荐

    python中尾递归用法实例详解_.docx

    尾递归之所以能被优化,是因为编译器在检测到函数为尾递归时,可以直接修改当前的活跃记录(即当前函数的栈帧)而不是在栈顶新增一个记录。这样做的好处是显而易见的: - 减少了内存的使用量。 - 避免了不必要的栈帧...

    Java SE程序 递归 Java SE程序 递归

    Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE...

    java 用递归实现字符串反转

    ### Java使用递归实现字符串反转 在Java编程语言中,递归是一种常用的方法来解决许多问题,特别是那些可以通过分解成更小子问题来解决的问题。本文将详细介绍如何使用递归来实现字符串的反转。 #### 一、递归基础...

    用Java集合递归实现通用树Tree

    本资源主要关注如何使用Java集合框架来递归实现一个通用的树结构,即`Tree`。下面我们将深入探讨这个主题。 首先,我们要了解Java集合框架。Java集合框架是Java语言提供的一组接口和类,用于存储和操作各种数据结构...

    java递归无限层级树

    在Java编程中,递归是一种强大的工具,常用于解决复杂问题,例如构建和遍历层次结构数据,如无限层级的树。在这个场景中,我们利用Java递归来表示一个树形结构,这种结构可以无限深入,每个节点可能包含子节点,也...

    C#中尾递归的使用、优化及编译器优化

    尾递归优化是指在递归调用位于函数体的最后,且没有其他操作的情况下,编译器或解释器可以将这种递归转换为迭代,从而避免堆栈空间的持续增长。例如,函数`TailRecursion`就展示了尾递归的使用,其中的递归调用位于...

    Java中递归逻辑循环调用解压zip里面所有的压缩包

    Java中递归逻辑循环调用解压zip里面所有的压缩包 Java中递归逻辑循环调用解压zip里面所有的压缩包

    java递归树型结构通用数据库

    "Java递归树型结构通用数据库" Java递归树型结构通用数据库是指使用Java语言实现的递归树型结构数据库系统,该系统可以实现树型结构的部门管理,包括部门的添加、删除、修改和查询等操作。 知识点: 1. 递归树型...

    java中递归用法详解

    java中递归的用法比较单一,但是用途比较重要,在开发中经常用到,熟练掌握递归的用法有利于程序代码的快速合理编写

    java实现递归调用

    因此,在使用递归时,要确保有一个明确的基线条件来终止递归,以及优化递归深度,避免无尽递归。 总结来说,Java通过递归调用来遍历树是一种常见的编程技巧,可以方便地实现前序、中序和后序遍历。同时,SQL虽然不...

    java 递归问题文档

    6. **尾递归优化**:某些Java编译器支持尾递归优化,这允许在不增加额外堆栈空间的情况下进行递归调用。不过,Java标准版目前并不默认开启这一优化,但在Java 14及以上版本的JDK中,可以使用`@jdk.internal.vm....

    关于java递归文件,以及检索特定文件

    在给定的标题“关于java递归文件,以及检索特定文件”中,我们可以推测这篇博文可能探讨了如何使用Java递归算法遍历文件系统,寻找特定类型的文件。下面将详细解释这个主题。 首先,让我们理解递归的概念。递归是一...

    python中尾递归用法实例详解

    本文实例讲述了python中尾递归用法。分享给大家供大家参考。具体分析如下: 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的...

    java递归

    遗憾的是,标准的Java并不支持尾递归优化。 6. **调试递归**:由于递归涉及多个函数调用,调试递归函数可能会比较复杂。使用调试器的步进功能可以帮助理解每个递归层级的执行过程。 举例来说,计算阶乘可以使用...

    Java递归算法构造JSON树形结构

    Java 递归算法构造 JSON 树形结构 Java 递归算法构造 JSON 树形结构是指通过 Java 语言使用递归算法将数据库中的菜单表构建成树形的 JSON 格式发送给第三方。这种方法可以将复杂的树形结构数据转换成易于理解和处理...

    JAVA程序递归方式搜索Windows文件夹源代码

    在Java编程中,递归是一种强大的技术,常用于解决复杂问题,例如遍历或搜索文件系统中的文件夹。本文将详细解析如何使用Java编写一个递归程序来搜索Windows文件夹,以及涉及到的相关知识点。 首先,我们需要理解...

    Java 递归法求5!阶乘相加之和.rar

    Java 采取递归方法求5!的阶乘,递归方法求阶乘之和,输入要阶乘的数字,递归公式:fn=fn_1*4! 具体来看以下代码:  System.out.print("输入要阶乘的数字:");  Scanner scanner = new Scanner(System.in);  int n ...

    Java 数组递归算法的复杂度

    ### Java 数组递归算法的复杂度 #### 内容概览 本文主要探讨了Java中几种常见的排序算法(冒泡排序、选择排序、插入排序、希尔排序)以及递归算法的时间复杂度分析。通过具体代码示例和理论分析,帮助读者理解不同...

    Java递归九宫格

    用递归的方法实现九宫格的初始化,可加深对二维数组传递参数的理解.

Global site tag (gtag.js) - Google Analytics