How do I do recursion?

There are 2 techniques that I can use to analyze a solution with recursion. I call the first one as Execution table. This techinque I learned from ThePrimegean - The last algorithm course you’ll need. Let’s say I have this code which is a solution for Merge two sorted linked list

Execution table

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;

  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

We can use these 2 linked lists for this code

const list1 = {"val":1,"next":{"val":2,"next":{"val":3,"next":null}}};
const list2 = {"val":1,"next":{"val":4,"next":{"val":5,"next":null}}};

The execution table would look like this

Picture1: Execution table

rA stands for return address for that function call, mTL is the short form of function mergeTwoLists, rV is return value and A is arguments. Final result of the linked list is 1 -> 1 -> 2 -> 3 -> 4 -> 5 or as javascript object, it should look like this

{
  "val": 1,
  "next": {
    "val": 1,
    "next": {
      "val": 2,
      "next": {
        "val": 3,
        "next": {
          "val": 4,
          "next": {
            "val": 5,
            "next": null
          }
        }
      }
    }
  }
}

but this technique can only work when there is one recursion for each execution. If there are more than one recursive function call, this table does not work. For example let us say that for one line, there are 2 recursive calls. Level 2 would have 2 function calls, level 3 would have 4 function calls and so on. The table will become unintuitive and hard to track. A tree structure appears to be more appropriate in this case

Execution tree

A good example for this mental model is question Climbing Stairs. The recursion answer is this

function climbStairs(n: number): number {
    return climb(0, n)
};

function climb(i: number, n: number): number {
    if (i === n) return 1;
    
    if (i > n) return 0;
    
    return climb(i + 1, n) + climb(i + 2, n)
}

For the value of n = 5, here is the execution graph

Picture2: Execution graph

If we sum all the number in red circles, the result is 8 which is the answer for n = 5. This is a good way to visualize recursion.

My friend once said that there must be a relationship between the base case and recursive case. So as boring a base case can be, it is very important to have a good base case because when the execution stack hits base case, it will start to return the value back to the caller and the chain of calculation will start. It seems the best way to test proper base case is to test the smallest input.