Returning from a Deep Recursion

Let us apply the idea discussed so far to write a factorial computation program. Click here to download a copy of this program.

#include  <stdio.h>
#include  <setjmp.h>

jmp_buf   JumpBuffer;

int       result;

void  main(int argc, char *argv[])
{
     int  n;

     n = (int) atoi(argv[1]);
     if (setjmp(JumpBuffer) == 0) 
          factorial(n);
     else
          printf("fact(%d) = %d\n", n, result);
     exit(0);
}

void  factorial(int n)
{
     fact(1, 1, n);
}

void  fact(int Result, int Count, int n)
{
     if (Count <= n)
          fact(Result*Count, Count+1, n);
     else {
          result = Result;
          longjmp(JumpBuffer, 1);
     }
}

• The main program reads in a value for n and uses function factorial(n) to compute the factorial of n. However, before calling factorial(n), a jump buffer is saved into JumpBuffer. Since this is the first time the execution flow passes through, setjmp() returns 0 and the flow goes down to the call to factorial(n).
• Function factorial(n) calls fact(1,1,n), which does the actual computation.
• We use a different way to write fact(Result,Count,n). The third argument, n, indicates that the expected result is n!. The first argument, Result, is used to accumulate product. More precisely, its value will be 1, 1*2, 1*2*3, ..., 1*2*3*...*n in the successive calls. Count is used as a counter.
• If Count is less than or equal to n, the desired factorial is not yet computed. Hence, the new result (i.e., Result*Count) and the new counter value (i.e., Count++) are sent to the next recursion level.
• Now the trick is here. If Count is larger than n, which means the factorial computation completes, fact() saves the final result into a global variable result and executes longjmp(JumpBuffer,1). This brings the control back to the main program. Thus, this skips all the tedious winding-up stage of the recursion.
• In the main program, setjmp() returns the value of the second argument of the corresponding longjmp() which is 1. Therefore, the else part is executed and prints out the value of the factorial.
• The following figure illustrates the winding down phase (in blue) and the short-cut (using longjmp()) winding-up phase (in red).
  

• The following figure shows the change of the execution stack for the call of factorial(4). When longjmp(JumpBuffer,1) executes, it sends the control back to the main program, and all activation records between the main program and the last call to fact() are reclaimed by the system. Consequently, the stack top pointer moves to the next available location beyond the main program's activation record.