問題描述有一個例子,給定一個鏈表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));
}當鏈表中的元素足夠大時,兩種遞歸的方法都會報堆棧溢出,為什么?如何優化尾遞歸,避免堆棧溢出?
添加回答
舉報
0/150
提交
取消