Tracing Recursion

Even more annoying than basic functions, tracing recursion aides in understanding code. Make sure you understand basic function tracing before you tackle this.

Back to Recursion

Tail End

• Again go line by line reading the code of the recursive function. Mark as you would a normal function, but quite often recursive functions are simple eloquent. There should be little to calculate within the function, and you should use a very small or no section.
• Set aside three columns. One is for function calls, the next is return values, and the final is evaluated returns.
• When the function is called, mark in the first column what arguments are used with an F().
• When you reach a return spot, mark in the second column (next to your call) what the return value is. If you make a call to the function, mark it in the first column and start anew. Use an R() to to distinguish returns from the calls.
• When you finally reach a simple return statement (no call), using the third column work your way back up to evaluate the returns of the second column.

double expo(double N, int pow)
{
   if(pow < 0)
      return 1 / expo(-N);
   else if(pow == 0)
      return 1;
   else(pow > 0)
      return N * expo(N, pow-1);	 				 				 		
} 

Simple, isn't it? Just take you time and be clear with your tracings.

Divide and Conquer

• This is the same are tail end but now you must keep track of several calls.
• Keep with one flow of the calls until you reach and end. More often than not it will give you the calls you skipped.
• If you did not cover all the specific calls trace down another flow. Don't forget to use the chart you make.

int Fibonacci(int N)
{
   if(N == 0 || N == 1)
      return 1;
   else
      return Fibonacci(N - 1) + Fibonacci(N - 2);		  
}

Back to Recursion

Prev -- Back to Portal -- Next