Confused about how tail recursion works?

Question

I'm using an example of adding two linked lists together from leetcode. The lists are in reverse order and the resulting list must be reversed as well. My code is recursive and it's only faster than 24% of the submissions.

I'm trying to learn how tail recursion works by applying it to my example. How would it improve its space or time complexity? Is it just a matter of eliminating the local variables and passing them as arguments?

/**
 * 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);
    }

Answer 1

Your recursive calls are not tail calls. Tail calls are those recursive calls that are the very last action the function performs.

With this algorithm that is not possible, because the list you get back from the recursive call is not the final result, nor can it be. You still need to prefix that returned list with the "current" node.

As you mention a low performance grade on LeetCode, you could look at some ways to improve the recursive implementation. As you mutate list l1, consider that you only need to create a new node, if an extra node is necessary because of overflow with carry beyond the final node. In all other cases it is possible to reuse the given nodes. In the case l2 is longer than l1, you can just rewire the remainder from l2 to the tail of l1 instead of padding with new ListNode(carry, null) instances.

Here is how that could look:

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;
    }
}

Secondly, the runtime ranking can fluctuate a lot on such platforms, so don't worry too much about it.

And finally, an iterative solution will certainly perform better.