4.8 Subroutines - Recursive

4.8 Subroutines - Recursive

4.8.1 Reading and Web Sites

1. Read about PUSHA, POPAin Intel's IA-32 Intel Architecture Software Developer's Manual
   Volume 2BA: Instruction Set Reference, N-Z. Pushes and pops all of the 32 bit registers at one time.
2. Read about ENTER, LEAVE In Intel's IA-32 Intel Architecture Software Developer's Manual
   Volume 2A: Instruction Set Reference, A-M. A high level procedure entry and exit instructions.

4.8.2 Notes

• The stack
  • return address
  • passed values
  • local variables
  • calling conventions
  • "C" calling convention. Variable number of arguments.
  • Pascal calling convention.
  • "gcc" calling sequence.
• Recursion

4.8.3 Lab Assignment, Subroutines

Write two programs. The first program is a set of subroutines called by a "C" program. The second is a main program that calls "C" functions.

1. Change my printfib.c program so that it prints your name, class (CIS250), the lab's name and the date. Remove the three subroutines. Here is the program that I wrote in "C".

   /* Louis Taber PCC 10/31/2004  C Fibonacci Program ver #1 */
   
   #include <stdio.h>
   int fibreset(void);
   int fib(int index);
   int fib2(int index);
   
   int fibcount;			/* keep track of number of calls */
   
   int main()
   {
   int i, f1, f2, f1c, f2c;
   
   fibreset();			/* Clear call count */
   
   printf("Louis Taber, PCC     C Fibonacci Program\n"
          "Compiled: " __DATE__ "  File: " __FILE__ "\n\n"
          "Index  Fibonacci    Calls    Fibonacci     Calls\n");
   
   for( i=0; i<=36; i++ )          /* First 36 numbers */
     {
     f1=fib(i);
     f1c=fibreset();
     f2=fib2(i);
     f2c=fibreset(); 
     printf("%5d %10d %10d    %10d %10d\n", i, f1, f1c, f2, f2c);
     }
   }
   
   int fibreset(void)		/* return old count */
     {
     int count;
   
     count = fibcount;
     fibcount = 0;			/* reset count */
     return count;
     }
   
   int fib(int index)		/* traditional recursive routine */
     {
     fibcount++;
     return index < 2 ? index : fib(index-1) + fib(index-2);
     }
   
   int fib2(int index)             /* faster recursive routine */
     {
     fibcount++;
   
     if( index == 14 ) return 377;
     if( index == 15 ) return 610;
     if( index == 28 ) return 317811;
     if( index == 29 ) return 514229;
     return index < 2 ? index : fib2(index-1) + fib2(index-2);
     }
   
   
   
   

   This is the output of the program.

   Louis Taber, PCC     C Fibonacci Program
   Compiled: Oct 31 2004    File: printfib.c
   
   Index  Fibonacci      Calls     Fibonacci      Calls
       0          0          1             0          1
       1          1          1             1          1
       2          1          3             1          3
       3          2          5             2          5
       4          3          9             3          9
       5          5         15             5         15
       6          8         25             8         25
       7         13         41            13         41
       8         21         67            21         67
       9         34        109            34        109
      10         55        177            55        177
      11         89        287            89        287
      12        144        465           144        465
      13        233        753           233        753
      14        377       1219           377          1
      15        610       1973           610          1
      16        987       3193           987          3
      17       1597       5167          1597          5
      18       2584       8361          2584          9
      19       4181      13529          4181         15
      20       6765      21891          6765         25
      21      10946      35421         10946         41
      22      17711      57313         17711         67
      23      28657      92735         28657        109
      24      46368     150049         46368        177
      25      75025     242785         75025        287
      26     121393     392835        121393        465
      27     196418     635621        196418        753
      28     317811    1028457        317811          1
      29     514229    1664079        514229          1
      30     832040    2692537        832040          3
      31    1346269    4356617       1346269          5
      32    2178309    7049155       2178309          9
      33    3524578   11405773       3524578         15
      34    5702887   18454929       5702887         25
      35    9227465   29860703       9227465         41
      36   14930352   48315633      14930352         67
   
   

2. Re-write the three subroutines used in printfib.c in assembly language.
   1. fibreset() -- resets global variables.
   2. fib() -- simple recursive Fibonacci function.
   3. fib2() -- enhanced recursive Fibonacci functions.
   Use the "C" calling convention.
3. Add the necessary global and extern statements.
4. Compile my modified program.
5. Assemble your subroutines.
6. Link the program, subprogram together.
7. Run the program. The output should be identical to my output.
8. Extra credit. Re-write the fib2 function used in printfib2.c, or printfib3.c in assembly language.

Turn in a printed error free listing of the assembly language programs & subprograms, a copy of the modified "C" main program, and the output of your program. Include a copy of any testing that you did to verify the program was correct.

4.8 Subroutines - Recursive