土成 2017-03-09 03:20 采纳率: 83.3%
浏览 1037
已采纳

effective java书中,为什么常规的递归克隆当链表过长时会导致栈溢出?

 public class HashTable implements Cloneable {  
    private Entry [] buckets = ... ;  

    public static class Entry {  
        final Object key ;  
        Object value ;  
        Entry next ;  

        public Entry(Object key, Object value, Entry next) {  
            this.key = key ;  
            this.value = value ;  
            this.next = next ;  
        }  

        // 递归地深层复制每个链表节点对象   
        Entry deepCopy() {  
            return new Entry(key, value,  
                    next == null ? null : next.deepCopy()) ;  
        }  
    }  

    @Override  
    public HashTable clone() {  
        try {  
            HashTable result = (HashTable) super.clone() ;  
            result.buckets = new Entry[buckets.length] ;  
            //采用循环的方式对每个桶引用的单链表进行深层拷贝  
            for (int i = 0; i < buckets.length; i++) {  
                if (buckets[i] != null) {  
                    result.buckets[i] = buckets[i].deepCopy() ;  
                }  
            }  
            return result ;  
        } catch(CloneNotSupportedException e) {  
            throw new AssertionError() ;  
        }  
    }  
    ...//其余方法省略  
}  

effective java书中说这种方法虽然灵活,但是针对列表中的每个元素,都要消耗一段栈空间。如果链表过长,就容易导致栈溢出。

而如果用迭代的话就可以避免:

 Entry deepCopy() {  
    Entry result = new Entry(key, value, next) ;  
    for (Entry p = result; p.next != null; p = p.next) {  
        p.next = new Entry(p.next.key, p.next.value, p.next.next) ;  
    }  
    return result ;  
}  

想知道为什么会出现栈溢出?用迭代为什么可以避免?求大神解答。

  • 写回答

2条回答 默认 最新

  • oyljerry 2017-03-09 03:32
    关注

    递归的时候,局部变量都分配在栈上,然后递归层数太多,就会导致栈上变量太多,导致空间不够溢出
    而迭代,每次迭代结束,局部变了会释放。就不会溢出了。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 VSCode里的Prettier如何实现等式赋值后的对齐效果?
  • ¥15 流式socket文件传输答疑
  • ¥20 keepalive配置业务服务双机单活的方法。业务服务一定是要双机单活的方式
  • ¥50 关于多次提交POST数据后,无法获取到POST数据参数的问题
  • ¥15 win10,这种情况怎么办
  • ¥15 如何在配置使用Prettier的VSCode中通过Better Align插件来对齐等式?(相关搜索:格式化)
  • ¥100 在连接内网VPN时,如何同时保持互联网连接
  • ¥15 MATLAB中使用parfor,矩阵Removal的有效索引在parfor循环中受限制
  • ¥20 Win 10 LTSC 1809版本如何无损提升到20H1版本
  • ¥50 win10 LTSC 虚拟键盘不弹出