Prelab 14

Name: __________________________

NetID:__________________________

Section: ______________



The following exercises cover the topic of recursion and should help you prepare for the in-lab activities. As with all prelabs/labs, if you are not sure of the answer you may go to any EWS lab on campus and check your results by using the gcc compiler, or you can ask anyone of the CS101 staff for help. In order to understand the material needed to answer these prelab questions please read the following material:

Part A: DMA

1. Fill in the blank below with the correct C code to dynamically allocate an array named arr that holds 20 elements of data type char and then copies the contents of the vegetable array into arr .
    

    char vegetable[] = "Rutabaga";
    char  *   arr;
   /* allocate space of 20 characters */

    arr  =  malloc(___________________________________________);


   
    /* copy the values of vegetable into into the new array */

    strcpy( arr ,  vegetable);

2. Fill in the blanks below with the correct C code to dynamically allocate an array named albums that holds 1000 elements of datatype Album.
    

	typedef struct 

	{    
    	   char  name[40];   /* track name or song name */    
    	   int   length;     /* in seconds */
	} Track;

	typedef struct 
	{    
	   int   cdno;       /* cd number */    
           char  title[30];  
           char  artist[20];    
           int   year;  
           int   num_tracks; /* number of tracks */    
           int   quantity;    
           float   price;    
           float   sales[MONTHS];  /* cd sales ($US) over the 12 months in 2005 */    
           Track   tracks[20]; /* info for each track */
        } Album;

    Album   * albums;

    albums  =  calloc(_________________ , __________________________);


Part B: Recursion

3. Write the  output the following program produces.

	#include <stdio.h>


	int   mystery( int n)
	{
    		if ( n <= 1)  /* Voom! --- means base case (or simplest) case of the problem */
        		return n;

    		else

       			return  mystery(n - 2);  /* mystery is a recursive function because it calls itself */

	}



	void main(void)

	{

  		printf(" %i  ", mystery(1));

  		printf(" %i  ", mystery(2));

  		printf(" %i  ", mystery(3));

  		printf(" %i  ", mystery(4));

  		printf(" %i  ", mystery(5));

	}


            ____________   ____________   ____________   ____________   _______________



4. Write the  output the following program produces.

	#include <stdio.h>


	int euclid( int a, int b)<

	{

   		if ( (a % b) == 0)  /* if b divides into a without remainder ...   Voom!*/
       			return b;
    		else
       			return euclid(b, a  %  b); 

 	}

	void main(void)
	{

  		printf(" %i  ", euclid(2,4));
  		printf(" %i  ", euclid(2,5));
  		printf(" %i  ", euclid(4, 16));
  		printf(" %i  ", euclid(12,18));
	}

            ____________    ____________    ____________    ____________ 



5.   Write the  output the following program produces.

	#include <stdio.h>

	int recFunc (int[], int);

	void main (void)
	{
    	int data[] = { 7, 6, 3, 8, 5, 9};
    	printf("%i \n", recFunc(data, 5));
	}

	int recFunc (int array[], int endpoint)
	{
    		int temp;
		if (endpoint == 0)  /* Voom! */
        		return array[0];
    		temp = recFunc(array, endpoint-1);
    		if (temp >= array[endpoint])
        		return temp;
    		return array[endpoint];
	}


             ________________________________________________ (Hint: the answer is a single number)







6. Fibonacci numbers are well-known in math and computer science. Each Fibonacci number is the sum of the two previous ones, yielding the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... . If we denote the nth Fibonacci number as Fn, then Fibonacci numbers are defined by the following set of equations:

F0 = 0, 
F1 = 1, 
Fn = Fn-1 + Fn-2   for n >= 2

Write a recursive function called fibonacci , which given integer argument n computes the nth Fibonacci number. 
int fibonacci(int n)
{
    
    /* Voom! check whether n equals 0 or n equals 1 */
    
    
 
     if ( _____________________  ||  ____________________ )
  


                return ______________________ ;  /* not 0 or 1 but something that depends on n */


   /* else use the formula for Fn shown above */    
        else  


                return _______________________________________________ ;


  
}


7. Binomial coefficients  (read 'n choose k') are used to denote the number of k-combinations of an n-set, which can be found using the formula  . Pascal's formula, written below
 
is a recursive way to compute binomial coefficients. Fill in the blanks to complete a recursive function named binomial , that given two integer arguments n and k computes and returns n choose k . We will assume that n >= k.

	#include <stdio.h>

	int binomial(int n, int k)

	{

		/* Voom! check whether n equals 0 or k equals 0 or n equals k */







		if( _______________________________________________________________ )


			return 1;


		else

		/* else use Pascal's formula shown above */




		
		return binomial(   n - 1 , __________________________________) + 


		binomial(________________________________________ , __________________________________);

	}




	void main(void)
	{

		printf("(0, 0) = %i \n", binomial(0,0)); /* prints 1 */

		printf("(1, 0) = %i \n", binomial(1,0)); /* prints 1 */

		printf("(1, 1) = %i \n", binomial(1,1)); /* prints 1 */

		printf("(10, 10) = %i \n", binomial(10,10)); /* prints 1 */

		printf("(3, 2) = %i \n", binomial(3,2)); /* prints 3 */

		printf("(4, 2) = %i \n", binomial(4,2)); /* prints 6 */

	}