Update: Note that as it stands this question does not make much sense, since the callstack will grow independently of the type T. The callstack solely depends on the number of nodes in the list being processed - the data contained in those nodes has no effect on the size of the callstack.
Let's say I have a recursive java implementation of a "remove-node-from-list" method which looks something like this:
// head
public void remove(T data) {
if (data == null)
throw new IllegalArgumentException();
head = remove(head, data);
}
// other nodes of list
private ListNode remove(ListNode current, T data) {
if (current == null)
return null;
if (current.data.compareTo(data) == 0)
return current.next;
current.next = remove(current.next, data);
return current;
}
Let's further assume that the type T is int
My question is: How large will the callstack get (in the worst-case) compared to the size of the list I'm processing?
What I've thought so far: From what I've seen Java 8 does not optimize recursions (right? my whole analysis assumes this to be true). Hence we will have a callstack growing linearly in with the size of the list.
More precisely: this method remove(ListNode current, T data) will basically put one node reference (32-Bits on 32-Bit arch) and an int (also 32-bit) on the callstack for each node in my list.
Now, since a node in the list also consists of one reference and one int a node has actually pretty much the same size as one of those recursive calls. Actually one of those calls might even use more space (the return address also has to be pushed onto the stack,right? or can this be optimized away somehow?).
So if I'm correct, then the callstack will basically get as large as the list itself in the worstcase (when the element to be removed is the last in the list)! Is this really the case? If I am correct then this would imply a factor of 1 or even larger with regard to the callstack required to process the list of ints! As a consequence, when processing large lists (actually not even that large), say 1M one will get a stackoverflow if one does run it with the default settings for stacksize (0.5M)
I'm aware of the fact that for larger data-types, the factor will be less, but still what I would stand firm on in any case is basically this: If there is no optimization going on, then the callstack will grow linearly with the size of the list - thus one should prefer the iterative over the recursive procedure.
In general I'd say, that the callstack will grow linearly roughly with a factor (size_of_all_arguments_in_call + size_of_return_address)/size_of_a_single_listelement which in the case of a list of ints is pretty much the same, right? Please don't get me wrong with the size_of_all_arguments: I know that we only pass the value of the references to the objects in those calls and not the whole objects themselves. Hence, for large objects, the factor might not be so dramatic but I'd still say one shouldn't accept that unnecessary linear space-overhead. However, for a list of ints the factor would be approx. 1.
Is this analysis correct or am I missing something?
Background: The person I was discussing this with, was trying to convince me that the callstack in java will not grow so dramatically and pointed out I was missing something obvious (unfortunately failed to tell me what and to me it really is not obvious at all) - since I don't know what it is I am missing I'm eager to learn ;)
Related:
The main thing missing in the related questions for me is how much space will the callstack actually use
