在Java中谈尾递归--尾递归和垃圾回收的比较(转载)

我不是故意在JAVA中谈尾递归的,因为在JAVA中谈尾递归真的是要绕好几个弯,只是我确实只有JAVA学得比较好,虽然确实C是在学校学过还考了90+,真学得没自学的JAVA好

不过也是因为要绕几个弯,所以才会有有意思的东西可写,另外还有我发现把尾递归如果跟JAVA中的GC比对一下,也颇有一些妙处(发现还没有人特地比较过)

(不过后来边写边整理思路,写出来又是另一个样子了)

一、首先我们讲讲递归

  1. 递归的本质是,某个方法中调用了自身。本质还是调用一个方法,只是这个方法正好是自身而已
  2. 递归因为是在自身中调用自身,所以会带来以下三个显著特点:
    1. 调用的是同一个方法
    2. 因为1,所以只需要写一个方法,就可以让你轻松调用无数次(不用一个个写,你定个n就能有n个方法),所以调用的方法数可能非常巨大
    3. 在自身中调用自身,是嵌套调用(栈帧无法回收,开销巨大)
  3. 因为上面2和3两个特点,所以递归调用最大的诟病就是开销巨大,栈帧和堆一起爆掉,俗称内存溢出泄露
    1. 一个误区,不是因为调用自身而开销巨大,而是嵌套加上轻易就能无数次调用,使得递归可以很容易开销巨大

既然会导致内存溢出泄露如此,那肯定要想办法了,方法很简单,那就是尾递归优化

二、尾递归优化

  1. 尾递归优化是利用上面的第一个特点“调用同一个方法”来进行优化的
  2. 尾递归优化其实包括两个东西:1)尾递归的形式;2)编译器对尾递归的优化
    1. 尾递归的形式
      1. 尾递归其实只是一种对递归的特殊写法,这种写法原本并不会带来跟递归不一样的影响,它只是写法不一样而已,写成这样不会有任何优化效果,该爆的栈和帧都还会爆
      2. 具体不一样在哪里
        1. 前面说了,递归的本质是某个方法调用了自身,尾递归这种形式就要求:某个方法调用自身这件事,一定是该方法做的最后一件事(所以当有需要返回值的时候会是return f(n),没有返回的话就直接是f(n)了)
      3. 要求很简单,就一条,但是有一些常见的误区
        1. 这个f(n)外不能加其他东西,因为这就不是最后一件事了,值返回来后还要再干点其他的活,变量空间还需要保留
          1. 比如如果有返回值的,你不能:乘个常数 return 3f(n);乘个n return n*f(n);甚至是 f(n)+f(n-1)
      4. 另外,使用return的尾递归还跟函数式编程有一点关系
    2. 编译器对尾递归的优化
      1. 上面说了,你光手动写成尾递归的形式,并没有什么卵用,要实现优化,还需要编译器中加入了对尾递归优化的机制
      2. 有了这个机制,编译的时候,就会自动利用上面的特点一来进行优化
      3. 具体是怎么优化的:
        1. 简单说就是重复利用同一个栈帧,不仅不用释放上一个,连下一个新的都不用开,效率非常高(有人做实验,这个比递推比迭代都要效率高)
  3. 为什么写成尾递归的形式,编译器就能优化了?或者说【编译器对尾递归的优化】的一些深层思想
    1. 说是深层思想,其实也是因为正好编译器其实在这里没做什么复杂的事,所以很简单
    2. 由于这两方面的原因,尾递归优化得以实现,而且效果很好
      1. 因为在递归调用自身的时候,这一层函数已经没有要做的事情了,虽然被递归调用的函数是在当前的函数里,但是他们之间的关系已经在传参的时候了断了,也就是这一层函数的所有变量什么的都不会再被用到了,所以当前函数虽然没有执行完,不能弹出栈,但它确实已经可以出栈了,这是一方面
      2. 另一方面,正因为调用的是自身,所以需要的存储空间是一毛一样的,那干脆重新刷新这些空间给下一层利用就好了,不用销毁再另开空间
    3. 有人对写成尾递归形式的说法是【为了告诉编译器这块要尾递归】,这种说法可能会导致误解,因为不是只告诉编译器就行,而是你需要做优化的前半部分,之后编译器做后半部分
  4. 所以总结:为了解决递归的开销大问题,使用尾递归优化,具体分两步:1)你把递归调用的形式写成尾递归的形式;2)编译器碰到尾递归,自动按照某种特定的方式进行优化编译

举例:

(没有使用尾递归的形式)

def recsum(x):
  if x == 1:
    return x
  else:
    return x + recsum(x - 1)

(使用尾递归的形式)

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

但不是所有语言的编译器都做了尾递归优化。比如C实现了,JAVA没有去实现

说到这里你很容易联想到JAVA中的自动垃圾回收机制,同是处理内存问题的机制,尾递归优化跟垃圾回收是不是有什么关系,这是不是就是JAVA不实现尾递归优化的原因?

三、所以下面要讲一下垃圾回收(GC)

  1. 首先我们需要谈一下内存机制,这里我们需要了解内存机制的两个部分:栈和堆。下面虽然是在说JAVA,但是C也是差不多的
    1. 在Java中, JVM中的栈记录了线程的方法调用。每个线程拥有一个栈。在某个线程的运行过程中, 如果有新的方法调用,那么该线程对应的栈就会增加一个存储单元,即栈帧 (frame)。在frame 中,保存有该方法调用的参数、局部变量和返回地址
    2. Java的参数和局部变量只能是 基本类型 的变量(比如 int),或者对象的引用(reference) 。因此,在栈中,只保存有基本类型的变量和对象引用。而引用所指向的对象保存在堆中。
  2. 然后由栈和堆的空间管理方式的不同,引出垃圾回收的概念
    1. 当被调用方法运行结束时,该方法对应的帧将被删除,参数和局部变量所占据的空间也随之释放。线程回到原方法,继续执行。当所有的栈都清空时,程序也随之运行结束。
    2. 如上所述,栈 (stack)可以自己照顾自己。但堆必须要小心对待。堆是 JVM中一块可自由分配给对象的区域。当我们谈论垃圾回收 (garbage collection) 时,我们主要回收堆(heap)的空间
    3. Java的普通对象存活在堆中。与栈不同,堆的空间不会随着方法调用结束而清空(即使它在栈上的引用已经被清空了)(也不知道为什么不直接同步清空)。因此,在某个方法中创建的对象,可以在方法调用结束之后,继续存在于堆中。这带来的一个问题是,如果我们不断的创建新的对象,内存空间将最终消耗殆尽。
    4. 如果没有垃圾回收机制的话,你就需要手动地显式分配及释放内存,如果你忘了去释放内存,那么这块内存就无法重用了(不管是什么局部变量还是其他的什么)。这块内存被占有了却没被使用,这种场景被称之为内存泄露
  3. 所以不管是C还是JAVA,最原始的情况,都是需要手动释放堆中的对象,C到现在也是这样,所以你经常需要考虑对象的生存周期,但是JAVA则引入了一个自动垃圾回收的机制,它能智能地释放那些被判定已经没有用的对象

四、现在我们就可以比较一下尾递归优化和垃圾回收了

  1. 他们最本质的区别是,尾递归优化解决的是内存溢出的问题,而垃圾回收解决的是内存泄露的问题
    1. 内存泄露:指程序中动态分配内存给一些临时对象,但是对象不会被GC所回收,它始终占用内存。即被分配的对象可达但已无用。
    2. 内存溢出:指程序运行过程中无法申请到足够的内存而导致的一种错误。内存溢出通常发生于OLD段或Perm段垃圾回收后,仍然无内存空间容纳新的Java对象的情况。
    3. 从定义上可以看出内存泄露是内存溢出的一种诱因,不是唯一因素。
  2. 自动垃圾回收机制的特点是:
    1. 解决了所有情况下的内存泄露的问题,但还可以由于其他原因内存溢出
    2. 针对内存中的堆空间
    3. 正在运行的方法中的堆中的对象是不会被管理的,因为还有引用(栈帧没有被清空)
      1. 一般简单的自动垃圾回收机制是采用 引用计数 (reference counting)的机制。每个对象包含一个计数器。当有新的指向该对象的引用时,计数器加 1。当引用移除时,计数器减 1,当计数器为0时,认为该对象可以进行垃圾回收
  3. 与之相对,尾递归优化的特点是:
    1. 优化了递归调用时的内存溢出问题
    2. 针对内存中的堆空间和栈空间
    3. 只在递归调用的时候使用,而且只能对于写成尾递归形式的递归进行优化
    4. 正在运行的方法的堆和栈空间正是优化的目标

最后可以解答一下前头提出的问题

  1. 通过比较可以发现尾递归和GC是完全不一样的,JAVA不会是因为有GC所以不需要尾递归优化。那为什么呢,我看到有的说法是:JAVA编写组不实现尾递归优化是觉得麻烦又没有太大的必要,就懒得实现了(原话是:在日程表上,但是非常靠后),官方的建议是不使用递归,而是使用while循环,迭代,递推

转载:博客园-阁刚广志,地址:http://www.cnblogs.com/bellkosmos/p/5280619.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java架构师进阶

BATJ架构师常见面试题汇总之一 让你瞬间升华起来

优点:性能比面向对象高,因为类调用时需要实例化,开销比较大,比较消耗资源;比如单片机、嵌入式开发、Linux/Unix等一般采用面向过程开发,性能是最重要的因素...

452
来自专栏小二的折腾日记

《effective C++》from line 1 to line 12

包含着最初的以c语言为基础的C,面向对象的C++,C++的泛型编程,以及STL。在我们使用的过程中,可能会穿插,但是我们需要根据不同的情况使用不同的策略。

673
来自专栏企鹅号快讯

编码,深浅copy

encode,decode在python2中使用的一些迷糊,python3中更容易理解 要理解encode和decode,首先我们要明白编码,字符和二进制的相关...

3176
来自专栏C语言C++游戏编程

零基础如何快速精通C语言?要注意什么?

困难的是,对于C语言,不论是数据类型、操作符、语句、函数,都或多或少、或简单或复杂地通过地址操作内存。

1032
来自专栏菩提树下的杨过

ActionScript3.0(AS3)中的泛型数组Vector

Adobe官方并没有"泛型数组"的叫法,这是我自己对Vector的叫法(有点标题党),不过Vector在使用上确实跟c#中的泛型数组有些相似之处。 我们知道:A...

1987
来自专栏极客猴

几个 Python 编程小技巧

我们在爬取网站是,会经常抓取网页文本,但是打印文本会出现是一堆乱码。这是为什么呢?原因是 Python 中字符对象分为两种,一种是 Unicode 对象,另一种...

562
来自专栏C/C++基础

C/C++ const

const是C语言的关键字,经C++扩充,功能变得强大,用法复杂。const用于定义一个常变量(只读变量)。当const与指针、引用、函数等结合起来使用时,情况...

891
来自专栏阿凯的Excel

Python读书笔记6(列表-基本特性)

前期和大家分享了数字和字符串,如果数字和字符串都是单一的个体的话,列表就是将多个数字和字符串组合在一起,形成列表。列表概念与数组概念类似,是包含任意对象的有序集...

2645
来自专栏机器学习从入门到成神

《你不知道的JavaScript》读书笔记(一)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

481
来自专栏take time, save time

初级程序员面试不靠谱指南(三)

二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

3169

扫码关注云+社区