How can I analyze a recursive source codes by hand?

How can I analyze a recursive source codes by hand?

For example, I have devised a technique for analyzing iterative source code by hand like this:

int fact(int n) 
{ 
 int f = 0; 
 int i = 0; 
 if (n<=1)  
 {  
  return 1; 
 } 

 f = 1; 
 i = 2; 
 for (i=2; i<=n ; i++) 
 { 
  f *= i; 
 } 

 return f; 
}

---------------------------
  i        开发者_开发百科 f       new-f
---------------------------
---------------------------
---------------------------

For each 'i' I can analyze and calculate the values of old-f and new-f by hand and fill up the table to see if the routine is working correctly.

But how can I analyze recursive routines by hand?

int fact(int number) {
    int temp;

    if(number <= 1) return 1;

    temp = number * fact(number - 1);
    return temp;
}

Since recursion stores values on the stack you need to analyze it 2-way

1st pass is: do the recursion until the termination condition is reached.

2nd pass: collect the values until the stack is empty.

1st down  2nd up
---------------------------------
n = 6     tmp = 6 * 120 = 720 <- result
n = 5     tmp = 5 * 24 = 120
n = 4     tmp = 4 * 6 = 24
n = 3     tmp = 3 * 2 = 6
n = 2     tmp = 2 * 1 = 2
n = 1     end

You can use a Debugger to do that without changing the origin codes or writing new codes. 1. Set a breakpoint at the address of function named fact 2. Run the debugger, each time when you stopped at the breakpoint, you can checkout the value of the parameter number, and the return value

When dealing with recursive functions, the way to effectively express what the function is doing is to view it as a mathematical function and simplify the application of the function. While this won't really tell you the internal state of the function (in this case, the value of temp) it gives you a really nice way to describe the function.

For factorial example, we can define fact to be:

fact(x) = 1 when x <= 1
fact(x) = x * fact(x - 1) otherwise

Now, when you want to express how it works, you choose a small starting number (say 6) and...

fact(6) = 6 * fact(5) = 6 * 5 * fact(4) = 6 * 5 * 4 * fact(3)

and so on.

This way, what you are doing is analyzing the structure of the function rather than its implementation. Now for debugging purposes this is not too useful (at least not in a non-functional language). But it's wonderful for comments, documentation and communication.