Recursion (Cambridge (CIE) A Level Computer Science): Exam Questions

The following recursive function is written in pseudocode. The line numbers are for reference only.

01 FUNCTION Total(N : INTEGER) RETURNS INTEGER

02    IF N = 1 THEN

03       RETURN 1

04    ELSE

05       RETURN N + Total(N - 1)

06    ENDIF

07 ENDFUNCTION

Identify the line number of the base case and the line number of the general case in the function Total().

The following function uses iteration to calculate the value of Base raised to the power Exponent. For example, Power(3, 4) returns 81.

Exponent is always 1 or greater.

FUNCTION Power(Base : INTEGER, Exponent : INTEGER) RETURNS INTEGER

   DECLARE Result : INTEGER

   DECLARE Count : INTEGER

   Result ← 1

   FOR Count ← 1 TO Exponent

      Result ← Result * Base

   NEXT Count

   RETURN Result

ENDFUNCTION

Write pseudocode for a recursive version of the function Power(). The function heading must stay the same.

The following recursive function is written in pseudocode.

FUNCTION DigitSum(Number : INTEGER) RETURNS INTEGER

   DECLARE Result : INTEGER

   IF Number >= 10 THEN

      Result ← (Number MOD 10) + DigitSum(Number DIV 10)

   ELSE

      Result ← Number

   ENDIF

   RETURN Result

ENDFUNCTION

In this function, MOD returns the remainder after integer division. DIV returns the whole-number quotient.

(i) Complete the trace table for the function when it is called as DigitSum(4739). The first row has been completed for you. Rows where a call returns to an earlier call are shown with its call number in brackets.

(ii) State the purpose of the function DigitSum().

A compiler translates a recursive function. When the program runs, the object code uses a stack to handle the recursive calls.

Name the process in which:

(i) the return address and the values of the local variables are pushed onto the stack with each recursive call, until the base case is reached

(ii) the return addresses and the values of the local variables are popped off the stack after the base case is reached.

The following pseudocode shows a recursive function and a statement that calls it. The line numbers are for reference only.

01 FUNCTION Steps(N : INTEGER) RETURNS INTEGER

02    IF N = 1 THEN

03       RETURN 0

04    ELSE

05       RETURN 1 + Steps(N DIV 2)

06    ENDIF

07 ENDFUNCTION

...

20 Answer ← Steps(12)

In this function, DIV returns the whole-number quotient.

Each time Steps() is called, the return address (the line number the call was made from) and the value of the parameter N are pushed onto a stack.

(i) Complete the table to show the contents of the stack at the moment the base case is reached. Row 1 is the top of the stack. You may not need all the rows.

(ii) State the value assigned to Answer on line 20.

The following recursive procedure is written in pseudocode.

PROCEDURE Show(N : INTEGER)

   IF N > 0 THEN

      OUTPUT N

      CALL Show(N - 2)

      OUTPUT N * 10

   ENDIF

ENDPROCEDURE

The procedure is called with the statement CALL Show(5)

(i) Write the output, in order, from this call.

(ii) The second group of values is output in the reverse order of the first. Explain, with reference to the stack, why this happens.