The three recursive functions are straightforward rewriting of the inductive definitions of the sequences. We also plan to keep track of the number of calls for each function on each argument value. Let us keep three global auxiliary arrays for that purpose. For this exercise arrays of size 26 suffice. But for allowing the possibility of accepting bigger inputs (n) let us stay prepared for n as big as 99.
int nA[100], nB[100], nC[100];On every occassion we want to count the numbers of calls, we should reset these counters to zeros. This can be handled by the following routine:
void resetCount ( int n )
{
int i;
for (i=0;i<=n;i++) nA[i] = nB[i] = nC[i] = 0;
}
Now one can implement the recursive routines A, B and C easily:
int A ( int n )
{
nA[n]++;
if (n==0) return(0);
if (n==1) return(1);
return(A(n/3)-2*B(n-2)+C(n));
}
int B ( int n )
{
nB[n]++;
if (n==0) return(-1);
if (n==1) return(0);
if (n==2) return(1);
return(n-A(n-1)+C(n-2)-B(n-3));
}
int C ( int n )
{
nC[n]++;
if (n==0) return(1);
return(B(n)-3*C(n/2)+5);
}
For handling [n/2] and [n/3] we have not required
any specific truncation commands. The argument n is
an integer variable. So n/2 and n/3 actually means
integer division, i.e., division followed by truncation. That's
what we want!
This part is a bit tricky. Look at the equations. Our strategy is to set the initial terms forcibly to the values supplied. Then we plan to calculate the next terms using the older values. Suppose that Ai, Bi and Ci are already computed for i=0,...,n-1. In the iterative step we use these values to compute An, Bn and Cn. An depends on Cn (and some Ai and Bj which are already computed). Cn, in turn, depends on Bn (and some older values). Finally, Bn can be computed using older terms that are all available at this point. Thus one must first compute Bn and then Cn and finally An. Incorporating these observations makes the iterative function work correctly.
void iterative ( int n )
{
int i;
int a[100], b[100], c[100];
a[0]=0; a[1]=1;
b[0]=-1; b[1]=0; b[2] = 1;
c[0]=1;
for (i=1;i<=n;i++) {
if (i>=3) b[i]=i-a[i-1]+c[i-2]-b[i-3];
c[i]=b[i]-3*c[i/2]+5;
if (i>=2) a[i]=a[i/3]-2*b[i-2]+c[i];
}
printf("a(%2d)=%d, b(%2d)=%d, c(%2d)=%d.\n",n,a[n],n,b[n],n,c[n]);
}
n = 25 Recursive method : A(25)=-137 Number of calls: A( 0): 4030280 A( 1): 2886293 A( 2): 4030280 A( 3): 1706147 A( 4): 794935 A( 5): 385211 A( 6): 189821 A( 7): 94249 A( 8): 46964 A( 9): 23442 A(10): 11711 A(11): 5853 A(12): 2926 A(13): 1463 A(14): 731 A(15): 366 A(16): 183 A(17): 91 A(18): 46 A(19): 23 A(20): 11 A(21): 6 A(22): 3 A(23): 1 A(24): 1 A(25): 1 B( 0): 7729526 B( 1):17582325 B( 2): 9167077 B( 3): 3699246 B( 4): 1665141 B( 5): 789815 B( 6): 384571 B( 7): 189741 B( 8): 94239 B( 9): 46962 B(10): 23442 B(11): 11711 B(12): 5853 B(13): 2926 B(14): 1463 B(15): 731 B(16): 366 B(17): 183 B(18): 91 B(19): 46 B(20): 23 B(21): 11 B(22): 6 B(23): 3 B(24): 1 B(25): 1 C( 0):14211037 C( 1):14211037 C( 2): 7582327 C( 3): 2929464 C( 4): 1285579 C( 5): 601327 C( 6): 290645 C( 7): 142857 C( 8): 70817 C( 9): 35256 C(10): 17590 C(11): 8785 C(12): 4391 C(13): 2194 C(14): 1097 C(15): 549 C(16): 274 C(17): 137 C(18): 69 C(19): 34 C(20): 17 C(21): 9 C(22): 4 C(23): 2 C(24): 1 C(25): 1 B(25)=105 Number of calls: A( 0): 3224015 A( 1): 2308886 A( 2): 3224015 A( 3): 1364831 A( 4): 635907 A( 5): 308148 A( 6): 151848 A( 7): 75394 A( 8): 37568 A( 9): 18753 A(10): 9368 A(11): 4682 A(12): 2341 A(13): 1170 A(14): 585 A(15): 293 A(16): 146 A(17): 73 A(18): 37 A(19): 18 A(20): 9 A(21): 5 A(22): 2 A(23): 1 A(24): 1 A(25): 0 B( 0): 6183220 B( 1):14064955 B( 2): 7333188 B( 3): 2959205 B( 4): 1332028 B( 5): 631811 B( 6): 307636 B( 7): 151784 B( 8): 75386 B( 9): 37567 B(10): 18753 B(11): 9368 B(12): 4682 B(13): 2341 B(14): 1170 B(15): 585 B(16): 293 B(17): 146 B(18): 73 B(19): 37 B(20): 18 B(21): 9 B(22): 5 B(23): 2 B(24): 1 B(25): 1 C( 0):11368096 C( 1):11368096 C( 2): 6065470 C( 3): 2343421 C( 4): 1028396 C( 5): 481031 C( 6): 232501 C( 7): 114278 C( 8): 56650 C( 9): 28203 C(10): 14071 C(11): 7028 C(12): 3512 C(13): 1755 C(14): 878 C(15): 439 C(16): 219 C(17): 110 C(18): 55 C(19): 27 C(20): 14 C(21): 7 C(22): 3 C(23): 2 C(24): 1 C(25): 0 C(25)=179 Number of calls: A( 0): 3224407 A( 1): 2309166 A( 2): 3224407 A( 3): 1364996 A( 4): 635984 A( 5): 308186 A( 6): 151866 A( 7): 75403 A( 8): 37573 A( 9): 18755 A(10): 9369 A(11): 4683 A(12): 2341 A(13): 1170 A(14): 585 A(15): 293 A(16): 146 A(17): 73 A(18): 37 A(19): 18 A(20): 9 A(21): 5 A(22): 2 A(23): 1 A(24): 1 A(25): 0 B( 0): 6183972 B( 1):14066662 B( 2): 7334079 B( 3): 2959565 B( 4): 1332189 B( 5): 631888 B( 6): 307674 B( 7): 151802 B( 8): 75395 B( 9): 37572 B(10): 18755 B(11): 9369 B(12): 4683 B(13): 2341 B(14): 1170 B(15): 585 B(16): 293 B(17): 146 B(18): 73 B(19): 37 B(20): 18 B(21): 9 B(22): 5 B(23): 2 B(24): 1 B(25): 1 C( 0):11369477 C( 1):11369477 C( 2): 6066207 C( 3): 2343705 C( 4): 1028521 C( 5): 481090 C( 6): 232529 C( 7): 114292 C( 8): 56657 C( 9): 28206 C(10): 14073 C(11): 7029 C(12): 3513 C(13): 1755 C(14): 878 C(15): 439 C(16): 219 C(17): 110 C(18): 55 C(19): 27 C(20): 14 C(21): 7 C(22): 3 C(23): 2 C(24): 1 C(25): 1 Iterative method : a(25)=-137, b(25)=105, c(25)=179.Mind-boggling, eh -- the number of times the functions are called, especially on smaller argument values. You must have observed a visible delay during the recursive computations, whereas the iterative function returns immediately (under your human perceptions!).
The three recursive functions are straightforward rewriting of the inductive definitions of the sequences. We also plan to keep track of the number of calls for each function on each argument value. Let us keep three global auxiliary arrays for that purpose. For this exercise arrays of size 26 suffice. But for allowing the possibility of accepting bigger inputs (n) let us stay prepared for n as big as 99.
int nA[100], nB[100], nC[100];On every occassion we want to count the numbers of calls, we should reset these counters to zeros. This can be handled by the following routine:
void resetCount ( int n )
{
int i;
for (i=0;i<=n;i++) nA[i] = nB[i] = nC[i] = 0;
}
Now one can implement the recursive routines A, B and C easily:
int A ( int n )
{
nA[n]++;
if (n==0) return(0);
if (n==1) return(1);
return(A(n/2)+B(n)-3*C(n-2));
}
int B ( int n )
{
nB[n]++;
if (n==0) return(1);
return(n-2*B(n/3)+C(n));
}
int C ( int n )
{
nC[n]++;
if (n==0) return(-1);
if (n==1) return(0);
if (n==2) return(1);
return(5-A(n-1)+B(n-2)-C(n-3));
}
For handling [n/2] and [n/3] we have not required
any specific truncation commands. The argument n is
an integer variable. So n/2 and n/3 actually means
integer division, i.e., division followed by truncation. That's
what we want!
This part is a bit tricky. Look at the equations. Our strategy is to set the initial terms forcibly to the values supplied. Then we plan to calculate the next terms using the older values. Suppose that Ai, Bi and Ci are already computed for i=0,...,n-1. In the iterative step we use these values to compute An, Bn and Cn. An depends on Bn (and some Ai and Cj which are already computed). Bn, in turn, depends on Cn (and some older values). Finally, Cn can be computed using older terms that are all available at this point. Thus one must first compute Cn and then Bn and finally An. Incorporating these observations makes the iterative function work correctly.
void iterative ( int n )
{
int i;
int a[100], b[100], c[100];
a[0]=0; a[1]=1;
b[0]=1;
c[0]=-1; c[1]=0; c[2] = 1;
for (i=1;i<=n;i++) {
if (i>=3) c[i]=5-a[i-1]+b[i-2]-c[i-3];
b[i]=i-2*b[i/3]+c[i];
if (i>=2) a[i]=a[i/2]+b[i]-3*c[i-2];
}
printf("a(%2d)=%d, b(%2d)=%d, c(%2d)=%d.\n",n,a[n],n,b[n],n,c[n]);
}
n = 25 Recursive method : A(25)=823 Number of calls: A( 0): 0 A( 1): 6689017 A( 2): 4779342 A( 3): 1909675 A( 4): 849225 A( 5): 399308 A( 6): 193424 A( 7): 95162 A( 8): 47195 A( 9): 23502 A(10): 11726 A(11): 5857 A(12): 2928 A(13): 1463 A(14): 731 A(15): 366 A(16): 183 A(17): 91 A(18): 46 A(19): 23 A(20): 11 A(21): 6 A(22): 3 A(23): 1 A(24): 1 A(25): 1 B( 0):15009286 B( 1): 8108518 B( 2): 6900768 B( 3): 2749776 B( 4): 1238632 B( 5): 589301 B( 6): 287609 B( 7): 142098 B( 8): 70630 B( 9): 35211 B(10): 17579 B(11): 8783 B(12): 4391 B(13): 2194 B(14): 1097 B(15): 549 B(16): 274 B(17): 137 B(18): 69 B(19): 34 B(20): 17 B(21): 9 B(22): 4 B(23): 2 B(24): 1 B(25): 1 C( 0): 8310151 C( 1):11639282 C( 2): 8528521 C( 3): 3530809 C( 4): 1621089 C( 5): 778528 C( 6): 381725 C( 7): 189033 C( 8): 94065 C( 9): 46921 C(10): 23433 C(11): 11709 C(12): 5853 C(13): 2926 C(14): 1463 C(15): 731 C(16): 366 C(17): 183 C(18): 91 C(19): 46 C(20): 23 C(21): 11 C(22): 6 C(23): 3 C(24): 1 C(25): 1 B(25)=-721 Number of calls: A( 0): 0 A( 1): 5350717 A( 2): 3823118 A( 3): 1527599 A( 4): 679317 A( 5): 319416 A( 6): 154725 A( 7): 76123 A( 8): 37752 A( 9): 18800 A(10): 9380 A(11): 4685 A(12): 2342 A(13): 1170 A(14): 585 A(15): 293 A(16): 146 A(17): 73 A(18): 37 A(19): 18 A(20): 9 A(21): 5 A(22): 2 A(23): 1 A(24): 1 A(25): 0 B( 0):12006315 B( 1): 6486213 B( 2): 5520102 B( 3): 2199618 B( 4): 990813 B( 5): 471397 B( 6): 230066 B( 7): 113668 B( 8): 56499 B( 9): 28166 B(10): 14062 B(11): 7026 B(12): 3512 B(13): 1755 B(14): 878 B(15): 439 B(16): 219 B(17): 110 B(18): 55 B(19): 27 B(20): 14 B(21): 7 B(22): 3 B(23): 2 B(24): 1 B(25): 1 C( 0): 6647503 C( 1): 9310563 C( 2): 6822184 C( 3): 2824385 C( 4): 1296751 C( 5): 622765 C( 6): 305351 C( 7): 151213 C( 8): 75245 C( 9): 37533 C(10): 18745 C(11): 9366 C(12): 4682 C(13): 2341 C(14): 1170 C(15): 585 C(16): 293 C(17): 146 C(18): 73 C(19): 37 C(20): 18 C(21): 9 C(22): 5 C(23): 2 C(24): 1 C(25): 1 C(25)=-748 Number of calls: A( 0): 0 A( 1): 5350679 A( 2): 3823091 A( 3): 1527588 A( 4): 679312 A( 5): 319414 A( 6): 154724 A( 7): 76122 A( 8): 37752 A( 9): 18800 A(10): 9380 A(11): 4685 A(12): 2342 A(13): 1170 A(14): 585 A(15): 293 A(16): 146 A(17): 73 A(18): 37 A(19): 18 A(20): 9 A(21): 5 A(22): 2 A(23): 1 A(24): 1 A(25): 0 B( 0):12006229 B( 1): 6486167 B( 2): 5520062 B( 3): 2199602 B( 4): 990806 B( 5): 471394 B( 6): 230064 B( 7): 113667 B( 8): 56498 B( 9): 28166 B(10): 14062 B(11): 7026 B(12): 3512 B(13): 1755 B(14): 878 B(15): 439 B(16): 219 B(17): 110 B(18): 55 B(19): 27 B(20): 14 B(21): 7 B(22): 3 B(23): 2 B(24): 1 B(25): 0 C( 0): 6647456 C( 1): 9310497 C( 2): 6822134 C( 3): 2824365 C( 4): 1296742 C( 5): 622760 C( 6): 305349 C( 7): 151212 C( 8): 75244 C( 9): 37533 C(10): 18745 C(11): 9366 C(12): 4682 C(13): 2341 C(14): 1170 C(15): 585 C(16): 293 C(17): 146 C(18): 73 C(19): 37 C(20): 18 C(21): 9 C(22): 5 C(23): 2 C(24): 1 C(25): 1 Iterative method : a(25)=823, b(25)=-721, c(25)=-748.Mind-boggling, eh -- the number of times the functions are called, especially on smaller argument values. You must have observed a visible delay during the recursive computations, whereas the iterative function returns immediately (under your human perceptions!).
int main ()
{
int i,n;
printf("n = "); scanf("%d",&n); printf("%d\n",n);
if (n<0) {
fprintf(stderr,"Error: I can not handle negative values of n.\n");
exit(1);
}
printf("Recursive method :\n");
resetCount(n);
printf("A(%d)=%d\n",n,A(n));
printf("Number of calls:\n");
for (i=0;i<=n;i++) printf("A(%2d):%8d%c",i,nA[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
for (i=0;i<=n;i++) printf("B(%2d):%8d%c",i,nB[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
for (i=0;i<=n;i++) printf("C(%2d):%8d%c",i,nC[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
resetCount(n);
printf("B(%d)=%d\n",n,B(n));
printf("Number of calls:\n");
for (i=0;i<=n;i++) printf("A(%2d):%8d%c",i,nA[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
for (i=0;i<=n;i++) printf("B(%2d):%8d%c",i,nB[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
for (i=0;i<=n;i++) printf("C(%2d):%8d%c",i,nC[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
resetCount(n);
printf("C(%d)=%d\n",n,C(n));
printf("Number of calls:\n");
for (i=0;i<=n;i++) printf("A(%2d):%8d%c",i,nA[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
for (i=0;i<=n;i++) printf("B(%2d):%8d%c",i,nB[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
for (i=0;i<=n;i++) printf("C(%2d):%8d%c",i,nC[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
printf("\nIterative method :\n");
iterative(n);
}
If the ugly sequence of formatted printf's appears unpleasant
to your eyes, you may rewrite main() using two satellite functions
as follows:
void printCallOne ( int n , int arrayName[] , char functionName )
{
int i;
for (i=0;i<=n;i++)
printf("%c(%2d):%8d%c",functionName,i,arrayName[i],(i%5==4)?'\n':' ');
if (i%5!=0) printf("\n");
}
void printCall ( int n )
{
printCallOne(n,nA,'A');
printCallOne(n,nB,'B');
printCallOne(n,nC,'C');
}
int main ()
{
int i,n;
printf("n = "); scanf("%d",&n); printf("%d\n",n);
if (n<0) {
fprintf(stderr,"Error: I can not handle negative values of n.\n");
exit(1);
}
printf("Recursive method :\n");
resetCount(n);
printf("A(%d)=%d\n",n,A(n));
printCall(n);
resetCount(n);
printf("B(%d)=%d\n",n,B(n));
printCall(n);
resetCount(n);
printf("C(%d)=%d\n",n,C(n));
printCall(n);
printf("\nIterative method :\n");
iterative(n);
}
[Course home] [Home]