Why is recursion faster than iteration in this implementation? (Python Reverse a Linked List)

user_9570941 0
Viewed 216

I have solved the "reverse a linked list" problem with both iterative and recursively. The results were unexpected for me. I am using leetcode so my iterative version beat the 27.7% of all the python3 submissions where as my recursive version beat the 95.97% of the solutions. I know that it might be due to tail call optimization but i do not understand HOW it could be. Could someone clarify this?

Here is my code for both of the implementations:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#def reverseList(self, head: ListNode) -> ListNode:
#            
#            prev = None
#            
#            while head:
#                headsNext = head.next
#                head.next = prev
#                prev = head
#                head = headsNext
#                
#            head = prev
#            
#            return head

class Solution:
    def reverseList(self, head: ListNode, prev = None) -> ListNode:

            if not head:
                return prev

            headsNext = head.next
            head.next = prev
            prev = head



            return self.reverseList(headsNext, prev)
linked-list python
1 Answers

I made a few performance tests and the two functions are very close to each other. This could make the differences fall in the error margins and give the impression that the recursive version is faster.

You can make sure that the iterative version is faster by reducing the number of assignments:

def reverseList1( head: ListNode) -> ListNode:            
    prev = None      
    while head:
        prev,head.next,head = head,prev,head.next                  
    return prev

Even if you do the same thing in the recursive function:

def reverseList2(head: ListNode, prev = None) -> ListNode:
    if not head: return prev
    prev,head.next,head = head,prev,head.next
    return reverseList2(head, prev)

EDIT After running the performance tests several times, the performance differences turn out to be insignificant. The iterative and recursive versions sometimes perform faster or not on each test run. This would mean that the speed scores are meaningless given that all versions perform identically given the margin of error.

user_52375600
Related