尾递归优化

1.什么是递归?

程序调用自身的编程技巧称为递归( recursion),就好像你做了一个梦,梦里面梦到梦到自己又做了一个梦,梦中梦。下面看一个例子:

public class JavaTest {

    public static int method(int num) {
        if (num > 1)
            return num + method(num - 1);
        else
            return num;
    }

    public static  void main(String[] args){
        int sum =method(100);//从一加到一百的和
        System.out.println(sum);
    }
}

这样递归的话呢,看上去代码很简洁,但是递归是存在缺点的,就是在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出。举个栗子,就是打开一扇门,然后又进去了一扇门,等到return的时候,会从里向外一个一个的return,一个一个的出来,所以之前的这些“门”是占要地方的,递归层级过深就会造成堆栈溢出。那么怎么解决这个问题呢?答案就是尾递归优化。

2.什么是尾递归?

如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。

public class JavaTest {
    public static int method(int num,int sum) {
        if (num > 1) {
            sum += num;
            return method(num - 1,sum);
        }
        else {
            return sum+1;
        }
    }
    public static int method(int num) {
        return method(num,0);
    }
    public static  void main(String[] args){
        int sum =method(100);
        System.out.println(sum);
    }
}

如上,使用了一个变量sum保存了递归调用的结果,并传到下一次递归调用中,这就是尾递归。到递归的结尾的时候,就可以直接return,不需要一层一层的出来。这样的话,就不用保存前面那些函数的堆栈,也就不会堆栈溢出了。

3.编译器的优化

虽然手写成了尾递归的形式,但是编译成字节码的时候,优不优化得看编译器的心情,所以很蛋疼。编译器如果支持尾递归优化,那么就会利用尾递归特点来进行优化,在递归调用的时候重复使用同一个函数栈帧,效率很高,however,java还没有实现尾递归优化的支持,官方是推荐使用循环,迭代,不使用递归。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,817评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,329评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,354评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,498评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,600评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,829评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,979评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,722评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,189评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,519评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,654评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,329评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,940评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,762评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,993评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,382评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,543评论 2 349

推荐阅读更多精彩内容

  • 以递归方式思考 递归通过灵巧的函数定义,告诉计算机做什么。在函数式编程中,随处可见递归思想的运用。下面给出几个递归...
    JasonDing阅读 1,433评论 0 1
  • 什么是尾递归 如果一个函数在定义时引用了自身,那么这个函数就是一个递归函数。例如我们所熟知的阶乘就可以通过递归函数...
    Liutos阅读 791评论 0 1
  • lua程序设计 书中原文 Lua中函数的另一个有趣的特征是可以正确的处理尾调用(proper tail recur...
    人气小哥阅读 3,675评论 0 0
  • 原文出处: neo1218 一般递归与尾递归 一般递归 执行: 可以看到, 一般递归, 每一级递归都需要调用函数,...
    PyChina阅读 1,906评论 1 8
  • “尾递归优化”的含义是:如果递归函数属于尾递归,那么运行时会优化其调用过程。优化主要针对调用栈,将多层调用,转化为...
    RocWay阅读 530评论 0 0