用尾递归求链表和，依然会出现堆栈溢出的情况

Question

问题描述

有一个例子，给定一个链表

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

希望用普通递归和尾递归两种方式计算链表元素之和，并验证当链表元素足够多时，普通递归出现堆栈溢出，而尾递归则不会出现

相关代码

add0() 方法采用普通递归的方式，add() 方法使用尾递归的方式。

public int add0(ListNode node) {
    if (node == null) {
        return 0;
    }
    return node.val + add0(node.next);
}

public int add(ListNode node, int result) {
    if(node == null) {
        return result;
    }
    result += node.val;
    return add(node.next, result);
}

你期待的结果是什么？实际看到的错误信息又是什么？

测试代码：

public void test() {
        ListNode node = new ListNode(0);
        ListNode temp = node;
        for (int i = 1; i < 1000000; i++) {
            temp.next = new ListNode(1);
            temp = temp.next;
        }
        System.out.println(add(node, 0));
//        System.out.println(add0(node));
    }

当链表中的元素足够大时，两种递归的方法都会报堆栈溢出，为什么？如何优化尾递归，避免堆栈溢出？

Answer 1

jvm 好像本来就不支持 TCO 吧？很长时间不看 java 了，如有错误，还望指正。

你可以用 python 试试，应该没什么问题。

Answer 2

写成尾递归的形式，并没有什么用，要真正的实现优化，还需要编译器中加入了对尾递归优化的机制。很显然java编译器没有对尾递归的代码进行编译优化。

Answer 3

java并没有尾递归优化…

Answer 4

建议使用Trampoline方式取代, 就是把递归转换成迭代