1.4 LEVELIZATION FOR THE PROCEDURAL PARADIGM

The program for the two-mortgage problem given in Example 1.2 is structured in that does not use goto statements, but it is still a flat piece of code. Repeated operations, al sections of code that logically belong together should be recoded as functions that can I tested independently.

Usually, this can be done in many different ways. The following example shows one possible way of improving the code from Example 1.2:

Example 1.4

#include <stdio.h>
#include <math.h>

int main(void){

  double pl,p2,il,i2,m,x;
  int n;
  void getInput(double*,double*,double*,double*,double*);
  double payment(double*,double,double);

  void prtResults(double,int,double,double);

  getInput(&pl,&p2,&il,&i2,&m);

  for(n=0; p1+p2>0; n++){
    if(i1*p1+i2*p2>=m)break;
    x=payment(&p1,i1,m);
    x=payment(&p2,i2,x);

  prtResults(p1+p2,n-1,m,m-x);
  return(0);
}

void prtResults(double cond,int num,double mon,double last){
  if(cond<=O){
    printf("\n%d payments of $ %8.2f\n",num,mon);
    printf("last payment   $ %8.2f\n",last);
  }
  else printf("\nmonthly payment too low to pay the interest\n");  }

double payment(double *p, double i, double m){
  double x;

  (*p)=(*p)+i*(*p);
  if((*p)>O){
  if((*p)<=m){x=m-(*p); (*p)=0;}
  else    {(*p)=(*p)-m; x=0;}
  else x m;
  return(x); /* money left after the payment */
}

void getInput(double *p1,double *p2, double *i1, double *i2, double *m){
  
  void getValue(char *,double*);
  double convertInterest(double);

  getValue("principal of the 1-st mortgage=",p1);
  getValue("interest  on the 1-st mortgage=",i1);
  getValue("principal of the 2-nd mortgage=",p2);
  getValue("interest  on the 2-nd mortgage=",i2);
  getValue("monthly payment               =",m);
  *i1=convertInterest(*i1);
  *i2=convertInterest(*i2);
}

void getValue(char *question,double *value){
  printf("%s=",question);
  scanf("%lf",value);
}

double convertInterest(double i){ return( pow(1+0.01*i, 1./12)-1. ); )

1. The program now has more lines. However, because its structure (logic) is emphasized, it is easier to read. Also, it can be tested in a modular fashion, starting from the lowest level functions.
2. The main program resembles the object-oriented version of the code (Example 1.3), except that more data is being passed between functions. This resemblance is due only to the small size of the problem; for a larger problem the two programs certainly would be quite different.
3. With many functions involved, functions themselves may be easy to understand and test, but the interaction between functions may become a problem. Programmers work- ing with large systems often use function calling diagrams, which display the relations between functions as a directed graph.

Figure 1.4 shows the basic calling diagram for Example 1.4. Calling diagrams may have various forms of sophistication, including showing information about the data which is being passed in and out of the functions (see [RUM], Chapter 6).

Figure 1.4 includes the standard library functions pow, scanf, and printf, to make this otherwise simple example more interesting. Note the simple organization of the calls, which is typical of most programs. Functions call only lower level functions, resulting in a lattice. A lattice differs from a tree in that the branches of two different children may con- verge to a common descendent, such as the function printf() in Figure 1.4. That is, if we removed printf from Figure 1.4, the diagram would be a tree.

If the calling diagram contains cycles, some of the functions must be directly or indi- rectly recursive. Compare Figures 1.5 and 1.6. Recursive cycles add dramatically to the complexity of the program and should be avoided, except for special situations. For more details on the negative effects of recursion on the efficiency of the code, allocation, and debugging, see [TIC]. This article also discusses the conditions that permit to convert recursion into iteration.

Figure 1.5 Function calling diagram in a well-structured program has a top-down flow, and no cycles.

Recursive functions may be more elegant from the point of view of formal understand- ing and semantics, but from the intuitive point of view, they are like feedback in engineer- ing systems, which may exhibit complex behavior that is often difficult to predict. Circuits having feedback often oscillate. [Feedback is an essential element of many systems, and cannot be eliminated. Positive feedback helps to amplify signals, negative feedback helps to stabilize systems.] Programs with recursive operation may easily fill up inter- nal stacks, overflow word size, or iterate forever, if we lose sight of what actually happens internally.

My personal strategy will be to avoid recursive functions, unless absolutely necessary. As a rule, I will never allow recursive calls over more than one stage. A function may call itself, but I will not allow more complex cycles, such as (f2-f6) or (f6-f8-f9) in Figure 1.6.

At stake here is not only code clarity, but also the ability to test individual functions independently. In Figure 1.5, the functions can be hierarchically tested in this order: f8, f9, fll, fl3, f7, flO, fl2, f3, f4, f5, f6, fl, and f2. Note that the order is a simple traversal of all functions, moving in horizontal layers from bottom to top. For example, when testing f3, we can trust that f7, fl O. and fl 1 already are working correctly.

In Figure 1.6, the recursive calls tie functions into groups that must always be tested together. Here f4, f5, {7, and f3 can be tested independently (in that order). Then f2, f6, fO, and f9 have to be tested simultaneously, and only after that, can fl be tested.

Figure 1.6 Funetion diagram with several recursive cyeles {f3, f2-f6, f6-f8-f9). Besides being very dif- fieult to understand, this program has the disadvantage that funetions f2, f6, f8 and f9 cannot be test- ed independently.

Nested function calls may be much less efficient than coding the algorithm directly, which in some situations is possible and not at all difficult. Let us look at a simple exam- ple: generating the Fibonacci numbers.

Example 1.5

Fibonacci numbers are defined by the following relations:

f[O] = 1
f[1] = 1
f[n] = f[n-1] + f[n-2]
This is a recursive definition, which translates into the following code:

fit fibonacci(int n){
   return(fibonacci(n-l) + fibonacci(n-2));
}

The function needs protection against overflowing the stack or word size:

int fibonacci(int n){
  int i;
  void report(void):

  if(n<=l)return(l);
  i=fibonacci(n-l);
  if(i==O)return(0):
  if(i>02777){report(); return(0);}
  i=i+fibonacci(n-2);
  return(i);
}

Now, when calculating fibonacci(10), this function is called 177 times, and needs an internal stack of 354 integers (2 for each call). For each call, the compiler stores the value of n, and allocates the automatic variable i.

In this particular case, the program can be implemented easily (and more efficiently) without using the recursive call:

int Fibonacci(int n) {
  int i,f1,f2,f3;
  void report(void);

  if(n<=1)return(1);
  f1=f2=1;
  for(i=2; i<=n; i++, f1=f2, f2=f3){
    if(f2>02777){report(); return(0);}
    f3=f1+f2:
  }
  return(f3);
}

A call to Fibonacci(10) executes only one function call, and requires internal storage of only five integers (n,i,f1,f2, and f3).

The Fibonacci numbers can also be calculated exactly, using the following formula:
f[n] = (((1 + a)/2)**n-((1-a)/2)**n)/a
where a = sqrt(5). The first term here rounds the correct integer, and the second term gives the exact error.

As you will see later, the levelization of function calls is even more important in object- oriented programs, where other dependencies, such as inheritance, may add to the com- plexity of design.