对尾递归的工作原理感到困惑？-解网

问：

我正在使用一个从 leetcode 将两个链表添加在一起的示例。列表的顺序相反，生成的列表也必须颠倒。我的代码是递归的，它只比 24% 的提交快。

我正在尝试通过将尾递归应用于我的示例来了解尾递归的工作原理。它将如何改善其空间或时间复杂度？是否只是消除局部变量并将它们作为参数传递？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode digit = null;

        int sum = l1.val + l2.val;
        int carry = sum / 10;
        int place = sum % 10;

        if (l1.next != null && l2.next != null) {
            l1.next.val += carry;
            digit = AddTwoNumbers(l1.next, l2.next);
        } else if (l1.next != null) 
            digit = AddTwoNumbers(l1.next, new ListNode(carry, null));
        else if (l2.next != null) 
            digit = AddTwoNumbers(new ListNode(carry, null), l2.next);
        else if (carry > 0)
            return new ListNode(place, new ListNode(carry, digit)); 

        return new ListNode(place, digit);
    }

C# 算法 Singlely-Linked-List Tail-Recursion

为了使方法符合尾递归的条件，递归调用必须是在每个可能的路径上执行的最后一条指令（或者根本不发生）。在您的代码中，情况并非如此，每个递归调用都必须返回，分配给，然后习惯于生成新的 .通常，通过将结果累积为函数的参数之一，传递它，并在最后返回它来解决此问题。另请注意，C# 编译器不会针对尾递归进行优化。有时，x86_64 JIT 会尝试这样做。digitListNode

答：

1赞 trincot 10/6/2023 #1

递归调用不是尾部调用。尾部调用是那些递归调用，是函数执行的最后一个操作。

使用这种算法是不可能的，因为从递归调用中返回的列表不是最终结果，也不可能是。您仍然需要在返回的列表前面加上“当前”节点。

当您提到 LeetCode 的低性能等级时，您可以考虑一些改进递归实现的方法。当您更改列表时，请考虑您只需要创建一个新节点，如果由于超出最终节点的进位溢出而需要额外的节点。在所有其他情况下，可以重用给定的节点。在的情况下，您可以只将余数从的尾部重新连接到的尾部，而不是用实例填充。l1l2l1l2l1new ListNode(carry, null)

这是它的样子：

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        if (l1.next == null && l2 != null) { // Swap, so l1 is not shorter than l2
            l1.next = l2.next;
            l2.next = null;
        }
        int sum = l1.val + (l2 == null ? 0 : l2.val);
        l1.val = sum % 10;
        if (sum > 9 || l2 != null && l2.next != null) {
            if (sum > 9 && l1.next != null) {
                l1.next.val++;
            }
            l1.next = l1.next != null ? AddTwoNumbers(l1.next, l2 == null ? null : l2.next) : new ListNode(1);
        }
        return l1;
    }
}

其次，在这样的平台上，运行时排名可能会波动很大，所以不要太担心。

最后，迭代解决方案肯定会表现得更好。

上一个：Leetcode 链表 II 问题 142.错误的解决方案，但它为什么有效？

下一个：为什么我无法分配并收到错误 AttributeError： 'NoneType' 对象没有属性 'next' slow.next=fast.next

对尾递归的工作原理感到困惑？

Confused about how tail recursion works?

评论