Call graphs

The call graph for any total function is a forest. A total function on the natural numbers, must have infinitely many nodes, and thus, it has a simple path of infinite length, infinitely many trees, or both. Every node has a simple path to some root, and so one way we can prove a function is total, is to find a function which bounds the length of the simple path for each input. We can augment any recursive function, whether it be total or not, to carry a counter that increments as we move towards the root. For example, here's a recursive function:

$$f(x) = \begin{cases} 0 & \text{if }x = 1 \\[0.4em] f(x / 2) & \text{if }x\text{ is even} \\[0.4em] f(3x + 1) & \text{if }x\text{ is odd} \end{cases}$$

Now let's augment it with a counter:

$$g(x, y) = \begin{cases} y & \text{if }x = 1 \\[0.4em] g(x / 2, y + 1) & \text{if }x\text{ is even} \\[0.4em] g(3x + 1, y + 1) & \text{if }x\text{ is odd} \end{cases}$$

To get the length of the path for \(x,\) we can evaluate \(h(x) = g(x, 0).\) Notice that if our original function \(f\) was a total function, then \(h\) must be a total function as well.