文档章节

Recursion and Tail Recursion in Java and Erlang

i
 iamtwang
发布于 2014/08/23 18:51
字数 348
阅读 142
收藏 1

Typical Recursion Example (hanoi problem)

public void move(int n, String strFrom, String strTemp, String strTo) {
        if (n == 1) {
            show(1, strFrom, strTo);
        } else {
            move(n - 1, strFrom, strTo, strTemp);
            move(n - 1, strTemp, strFrom, strTo);
        }
    }


Then I come cross the term recursion and tail recursion in Erlang.

%% recursion
sum([H|T]) ->
    H + sum(T);
sum([]) ->
    0.
%% tail recurion
sum(X) ->
    sum(X, 0).
sum([H|T], Acc) ->
   sum(T, H + Acc);
sum([], Acc) ->
    Acc.

What is A Tail Call?

A tail call is a fancy term that refers to a situation in which a method or function call is the last instruction inside of another method or function.

Recursion Code with Java.

     /**
     * sum from 1 to n. recursion
     * @param i
     * @return sum 
     */
    public int recur_head(int i){
        if(i==1)
            return 1;
        else
            return i+recur_head(i-1);
    }

Tail Recursion Code with Java.

    /***
     * sum from 1 to n. tail recursion
     * @param i
     * @param total
     * @return
     */
    public int recur_tail(int i, int total){
        if (i == 1)
            return 1+total;
        return recur_tail(i-1, total +i);
        
    }

See the class with

 javap -c
public class Recur {
  public Recur();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public int recur_head(int);
    Code:
       0: iload_1
       1: iconst_1
       2: if_icmpne     7
       5: iconst_1
       6: ireturn
       7: iload_1
       8: aload_0
       9: iload_1
      10: iconst_1
      11: isub
      12: invokevirtual #2                  // Method recur_head:(I)I
      15: iadd
      16: ireturn

  public int recur_tail(int, int);
    Code:
       0: iload_1
       1: iconst_1
       2: if_icmpne     9
       5: iload_2
       6: iconst_1
       7: iadd
       8: ireturn
       9: aload_0
      10: iload_1
      11: iconst_1
      12: isub
      13: iload_2
      14: iload_1
      15: iadd
      16: invokevirtual #3                  // Method recur_tail:(II)I
      19: ireturn
}


for Java Developer

Java programmers tend to avoid recursion through the use of loops.

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


Reference

http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044


© 著作权归作者所有

上一篇: Erlang Basic
下一篇: Tomcat Reading Notes
i
粉丝 0
博文 18
码字总数 7670
作品 0
英国
私信 提问
加载中

评论(1)

yanchao90
yanchao90
呵呵
Apache Tomcat 9.0.12 和 8.5.34 版本发布

Apache Tomcat 是 Java Servlet、JavaServer Pages、Java 表达式语言和 Java WebSocket 技术的开源实现,是一个免费的开放源代码的 Web 应用服务器。 Apache Tomcat 9.0.12 和 8.5.34 两个版...

王练
2018/09/12
1K
0
Spring boot中关于多对多查询json无限递归问题

控制台异常 父类 BusinessTemplate.java 子类 Link.java 问题描述 如果在LinkController中直接查询Link对象会出现json无限递归问题。 @JsonIdentityInfo解决 分别在父子类中添加如下注释:Bu...

亚林瓜子
2018/07/20
0
0
"Becoming Functional" 阅读笔记+思维导图

是O'Reilly公司今年(2014)7月发布的一本薄薄的小册子,151页,介绍了函数式编程的基本概念.全书使用代码范例都是基于JVM的编程语言,比如Java,Groovy,Scala.为了能够讲解所有的知识点,作者不得不...

唐玄奘
2017/12/08
0
0
MYSQL 存储过程中 执行游标里的动态SQL 如何破?

我有一个需求: 需要执行MYSQL数据库中配置的SQL,不使用JAVA调用,直接在存储过程中使用游标访问,执行动态的结果 在游标遍历循环里写如下代码: set @V_SQL= CONCAT(' ',V_SQL,' '); PREPA...

battier
2015/12/24
1K
4
Apache Qpid Python 1.35.0 发布

Apache Qpid Python 1.35.0 发布了,Apache Qpid (Open Source AMQP Messaging) 是一个跨平台的企业通讯解决方案,实现了高级消息队列协议。提供了 Java、C++ 两种服务端版本以及 Java、C++...

凝小紫
2016/08/31
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot 2 快速教程:WebFlux 集成 Mongodb(四)

摘要: 原创出处 https://www.bysocket.com 「公众号:泥瓦匠BYSocket 」欢迎关注和转载,保留摘要,谢谢! 这是泥瓦匠的第104篇原创 文章工程: * JDK 1.8 * Maven 3.5.2 * Spring Boot 2.1....

泥瓦匠BYSocket
40分钟前
2
0
$_ENV

$_ENV数组中的内容是在PHP解析器运行时,从PHP所在服务器中的环境变量, 导入到PHP的全局命名空间, 转变为PHP全局变量。 这些变量很多是由支持 PHP 运行的 Shell 提供的,并且不同的系统很可能...

vinci321
54分钟前
2
0
Guava RateLimiter + AOP注解实现单机限流、统计QPS

1、基于springboot项目pom.xml添加如下依赖: <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-aop</artifactId></dependency><d......

铁骨铮铮
今天
3
0
JAVA NIO Connection reset by peer 异常

客户端主动断开与服务端的连接,但是如果客户端掉线,服务端就接收不到了。。 异常信息 java.io.IOException: Connection reset by peerat java.base/sun.nio.ch.FileDispatcherImpl.read...

Jeremy_pan
今天
2
0
龙芯版办公软件下载

金山wps office   rpm包:http://ftp.loongnix.org/os/loongnix/1.0/os/Packages/w/wps-office-10.8.0.6472-1.a20p1.mips64el.rpm   deb包:http://packages.deepin.com/loongson/pool/......

gugudu
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部