Which is better in terms of memory usage (or in general)?

1. Using Recursion and having stack implementation (OS-implicit)
2. Using Iteration and having stack implementation (explicit)

A sample code for a question on Leetcode named 1265. Print Immutable Linked List in Reverse is given below.

class Solution:
    """Recursion"""

    def printLinkedListInReverse(self, head: "ImmutableListNode") -> None:
        if head:
            self.printLinkedListInReverse(head.getNext())
            head.printValue()


class Solution:
    """Iteration"""

    def printLinkedListInReverse(self, head: "ImmutableListNode") -> None:
        stack = []
        while head:
            stack.append(head)
            head = head.getNext()
        while stack:
            stack.pop().printValue()

Please contrast the above code in terms of memory usage.

CodePudding user response：

The recursive version of your code takes more memory, because it stacks the local variables, and there are two of them: self and head.

In the iterative version of your code, the explicit stack only has references of head.

The situation would improve if the function were not a method of Solution, but this is a pattern that is at the heart of the LeetCode testing framework.

Another consideration is that the call stack is limited in size. So if the input is large, then the recursive version is not an option.

Now, this doesn't say anything about the speed of the program. It might still be that the recursive version runs faster, depending on the interpreter.

CodePudding user response：

As a rule, recursion takes more memory than iteration. See for example

https://webrewrite.com/iteration-versus-recursion-which-one-you-choose

For large datasets I always use iteration.