Dec1999 CA208 : 'C' Programming (Question 4)Suggested Solutions

(a)

Explain the difference between recursion and iteration.

•Recursion is when a procedure or function calls itself,with new values for parameters;(1 mark)

•Iteration is when a group of statements are looped through until a condition or counter is reached;(1 mark)

[2]

(b)

In a recursive function,the recursive call should always be guarded by a test.Briely explain what would normally be tested for,and why it is necessary.

•Normally,the data passed into the recursive call is tested for some terminating condition;(1 mark)

•It is necessary to stop the function from recursing infinitely.
(1 mark)

[2]

(c)

Give an example of a construct which is used to write an iterative loop.

•for loop;(1 mark)

•while loop;(1 mark)

[1]

(d)

Identify the difference between call by reference and call by value parameter passing.

•In call by reference,changes made by the procedure or function to parameters are reflected in the calling section of code;(1 mark)

•In call by value,the changes made by the procedure or function to the parameters are not reflected in the calling section of code.
(1 mark)

[2]

(e)

The mathematical expression x y is computed by multiplying x by itself,y times.Write a recursive procedure,called power ,the signature of which is given below,which takes in an integer x and an integer y by reference,and on exit the value of x is x y .On exit the value of y should remain unchanged.

void power(int*x,int*y);

A sample definition of power follows:

void power(intx,inty) {
	*int z=x; if((y)!=1){*
		(y)=(y)-1; power(x,y); (x)=z (x); (y)=(*y)+1;
	}
}

And the following marking scheme should be used:

•Declaring a local temporary variable;(1 mark)

•Which is used to store the original value pointed to by x ;(1 mark)

•Including a statement to test the base condition;(1 mark)

•Correctly specifying the base condition on y (1 mark)

•Reducing the value pointed to by y by one,to count down to the base case; (1 mark)

•Recursing with the unchanged value of x and the decremented value of y ; (1 mark)

•Multiplying the original value of x by the value at that level of recursion,thereby calculating the power;(1 mark)

•Incrementing the value of y as the recursive stack is climbed back,to ensure its value is unchanged on exit.(1 mark)

[8]