Mastering Algorithms with C

120813

1. structures are not permitted to contain instances of themselves, but they may contain pointers to instances of themselves.

120814

1. tail resursion : much faster and memory saving method than the general recursion. general recursion form can be simply modified to tail recursion form usually. need to be mastered!

 A recursive call is tail recursive when it it the last statement that will be executed within the body of a function and its return value is not a part of an ｅxpression. Tail recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take advantage of it.

a. general recursion form of factorial computation

int fact(int n)

{

if(n < 0) 

return 0;

else if(n == 0) 

return 1;

else if(n == 1) 

return 1;

else 

return n*fact(n-1);

}

b. tail recursion form of factorial computation

int facttail(int n, int a)

{

if(n < 0)

return 0;

else if(n == 0)

return 1;

else if(n == 1)

return a;

else

return fact(n-1, n*a);

}

Note that there is an another argument necessary to maintain the intermediate computation result.