为什么在这个实现中递归比迭代快？

Question

我已经通过迭代和递归解决了“反向链表”问题。结果出乎我的意料。我正在使用 leetcode，所以我的迭代版本击败了所有 python3 提交的 27.7%，而我的递归版本击败了 95.97% 的解决方案。我知道这可能是由于尾调用优化，但我不明白它是怎么回事。有人可以澄清一下吗？

这是我的两种实现的代码：

# 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)

Answer 1

我做了一些性能测试，这两个功能非常接近。这可能会使差异落在误差范围内，并给人以递归版本更快的印象。您可以通过减少分配的数量来确保迭代版本更快：def reverseList1( head: ListNode) -> ListNode:                prev = None          while head:        prev,head.next,head = head,prev,head.next                      return prev即使你在递归函数中做同样的事情：def reverseList2(head: ListNode, prev = None) -> ListNode:    if not head: return prev    prev,head.next,head = head,prev,head.next    return reverseList2(head, prev)编辑 多次运行性能测试后，性能差异变得微不足道。迭代和递归版本有时在每次测试运行时执行得更快或不执行。这意味着速度分数毫无意义，因为所有版本在误差范围内都表现相同。