1 Understanding recursive code in C

1.1 In the original (terse) form

Let us sum of natural numbers \(f(n)=\sum_{i=0}^{n} i\) as an example of how to understand recursive C code. In the most concise way, This function can be written as follows:

unsigned f(unsigned n)
{
  return (n == 0) ? 1 : n+f(n-1);
}

Even in this form a debugging, such as gdb, can still be helpful to understand how the function calls itself. Putting a breakpoint on the entry point of the function (the unsigned f(unsigned n line) can help with understanding how the function calls itself. gdb automatically shows the parameters for each invocation when breaking at the entry point of a function, and the command bt (back trace) is very helpful to understand the path to the current invocation of the function.

1.2 Spelling out the recursive definition

To facilitate better understanding and debugging, this function can be rewritten as follows:

unsigned f(unsigned n)
{
  unsigned result;
  if (n == 0) {
    result = 1;
  }
  else {
    result = f(n-1);
    result = n+result;
  }
  return result;
}

This version of the function uses may statements to accomplish the same effect as a single ternary expression. gdb and most debuggers are generally line/statement oriented. As a result, this rather verbose version of this function makes it possible to single step and debug the code in finer granularity.

Using this format, it is easier to use gdb to single step through the code and actually visualize the calling and returning of invocations of the function.

Of course, for those who prefer to debug using cout, this spelled out version allows many additional points to insert cout statements.

2 Coding in TTPASM

The key to effective programming is to implement-test-debug incrementally. Using the example from the previous section, the first function to implement may only look like the following:

unsigned f(unsigned n)
{
  unsigned result;
  result = n+42;
  return result
}

While this function has nothing to do with the function that we need to implement, if the TTPASM implementation works correctly, then we confirm the following rather important parts:

• access to parameter n is correct
• the allocation and deallocation of local variable result is correct
• access to local variable result is correct
• the computation of n+42 is correct, and
• returning the result is correct

Test cases for this revision may include f(3), f(20), etc.

The next revision of function f to implement may look like the following:

unsigned f(unsigned n)
{
  unsigned result;
  if (n==0) {
    result = 1;
  }
  else {
    result = n+42;
  }
  return result;
}

This revision adds the complexity of the conditional statement. Two important test cases are f(0) and f(1). The former test case should return a value of 1, while the second should return a value of 43.

The next revision of function f may look like the following:

unsigned f(unsigned (n)
{
  unsigned result;
  if (n==0) {
    result = 1;
  }
  else {
    result = f(n-1);
  }
  return result;
}

In this case, the importance is that the TTPASM code handles the recursive calls and returns correctly. The test case f(0) and f(3) all return a value of 1, but the use of the stack will be quite different.

Given that the function is implemented correctly up to this point, then the next revision can be the actual code.

Once the function is fully implemented, it is still important to first test with the non-recursive case of f(0), then f(1), etc.

3 Working out Fibonnaci invocations manually

The following is just an example for f(4) where f is the function computing the Fibonnaci number:

• f(4) return 3
  • `f(3) return 2
    • `f(2) return 1
      • f(1) return 1
      • f(0) return 0
    • `f(1) return 1
  • f(2) return 1
    • f(1) return 1
    • f(0) return 0