How can I parse recursive source codes manually?

Question

How can I analyze recursive source codes manually?

For example, I developed a method for analyzing iterative source code manually as follows:

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; } --------------------------- if new-f --------------------------- --------------------------- --------------------------- 

For each "i", I can analyze and calculate the values ​​of old-f and new-f manually and populate the table to make sure that the procedure works correctly.

But how can I parse recursive routines manually?

 int fact(int number) { int temp; if(number <= 1) return 1; temp = number * fact(number - 1); return temp; } 

Answer 1

Since recursion stores values ​​on the stack, you need to analyze it in 2 directions

First pass: do a recursion until a termination condition is reached.

2nd pass: collect 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 

Answer 2

You can use the debugger for this without changing the origin codes or writing new codes. 1. Set a breakpoint at the address of the function called the fact 2. Run the debugger, each time you stop at the breakpoint, you can check the value of the parameter number and the return value

Answer 3

When working with recursive functions, the way to effectively express what the function performs is to consider it as a mathematical function and simplify the application of the function. Although this does not really tell you about the internal state of the function (in this case, the value is temp ), it gives you a very good way to describe this function.

For factorial, we can determine the fact:

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

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

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

etc.

Thus, what you do is an analysis of the structure of the function, not its implementation. Now for debugging purposes this is not very useful (at least not in a non-functional language). But this is great for comments, documentation, and communication.