How a variable flows in recursion?

Question

This is a LeetCode question, what is asked is to sum up two linked numbers, for example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Question:
The following code use recursive method, every recursive call (the third to last line) will construct a new result, I am having difficulties to wrap my head around that why would the old result not be overwritten by the new result? Is it because these results belong to different scopes, for example, scope1.result, scope2.result?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public ListNode op(ListNode l1, ListNode l2, int carry) {

    if (l1==null && l2==null) {
        return carry==0 ? null: new ListNode(carry);
    }

    if (l1==null && l2!=null) {
        l1 = new ListNode(0);
    }

    if (l1!=null && l2==null) {
        l2 = new ListNode(0);
    }

    int sum = l1.val + l2.val + carry;
    ListNode result = new ListNode(sum % 10);
    result.next = op(l1.next, l2.next, sum / 10);
    return result;
}

What you are looking for is called the [stack frame](https://stackoverflow.com/questions/10057443/explain-the-concept-of-a-stack-frame-in-a-nutshell) (or *callstack*). — Elliott Frisch, Jul 11 '17 at 01:34

score 0 · Accepted Answer · answered Jul 11 '17 at 11:47

Local variables are unique to the call. Thus if you are doing this with two linked lists of length 3 you'll have 4 result and sum that are local to their instance of the call.

In fact recursive functions are not getting any special treatment in Java. Every function gets their own local variables and parameters. eg.:

public int test1(int n) {
  int y = 2*n;
  return y + test2(n+1);
}

public int test2(int n) {
  int y = 3*n;
  return y - n/3;
}

This is not recursive at all but both has the variable n and y. If variables were not local test1(3) would have become 23 since test2 would have altered test1's y, but since both n and y are local to each method call y stays 6 and with 15 as result.

If a method calls itself if gets a new set of variables for that run and when it returns the variables of the callee is the same as before.

This applies to variable bindings and not objects. If you were to pass an object to a method and it mutated the object and not the binding your change will affect all variables that points to that object. eg.

// Bad implementation of rounding up to nearest 10 by mutating box
public int test(int[] n) {
  if( n[0] % 10 == 0)
    return n[0];
  n[0]++; // mutates array not binding
  return test(n);
}

A better recursive version:

public int test(int n) {
  if( n % 10 == 0)
    return n;
  return test(n+1);
}

How a variable flows in recursion?

1 Answers1