用尾遞歸求鏈表和，依然會(huì)出現(xiàn)堆棧溢出的情況

問題描述

有一個(gè)例子，給定一個(gè)鏈表

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

希望用普通遞歸和尾遞歸兩種方式計(jì)算鏈表元素之和，并驗(yàn)證當(dāng)鏈表元素足夠多時(shí)，普通遞歸出現(xiàn)堆棧溢出，而尾遞歸則不會(huì)出現(xiàn)

相關(guān)代碼

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);
}

你期待的結(jié)果是什么？實(shí)際看到的錯(cuò)誤信息又是什么？

測(cè)試代碼：

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));
    }

當(dāng)鏈表中的元素足夠大時(shí)，兩種遞歸的方法都會(huì)報(bào)堆棧溢出，為什么？如何優(yōu)化尾遞歸，避免堆棧溢出？