problem description
there is an example, given a linked list
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}I hope to calculate the sum of linked list elements by ordinary recursion and tail recursion, and verify that when there are enough linked list elements, stack overflow occurs in ordinary recursion, but not
in tail recursion.related codes
Theadd0 () method uses normal recursion. The, add () method uses tail recursion.
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);
}what result do you expect? What is the error message actually seen?
Test Code:
public void test() {
ListNode node = new ListNode(0);
ListNode temp = node;
for (int i = 1; i < 1000000; iPP) {
temp.next = new ListNode(1);
temp = temp.next;
}
System.out.println(add(node, 0));
// System.out.println(add0(node));
}when the elements in the linked list are large enough, both recursive methods report a stack overflow. Why? How to optimize tail recursion to avoid stack overflow?