Skip to content
MarkSchemeMarkScheme
Sign up — no card

9618 · 19.2

Recursion — practice questions

Practice and worked examples for 9618 Recursion. Short previews only — attempt the full question in MarkScheme against the official scheme.

Worked example 1

Write a recursive function in pseudocode, Factorial(n), that calculates the factorial of a non-negative integer nn. Trace the execution for Factorial(4).

Show solution outline
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
  IF n = 0 THEN
    RETURN 1  // Base Case
  ELSE
    RETURN n * Factorial(n - 1)  // Recursive Step
  ENDIF
ENDFUNCTION

Execution Trace for Factorial(4):

  1. Factorial(4) is called. Since 4 ≠ 0, it computes 4 * Factorial(3).
  2. Factorial(3) is called. Since 3 ≠ 0, it computes 3 * Factorial(2).
  3. Factorial(2) is called. Since 2 ≠ 0, it computes 2 * Factorial(1).
  4. Factorial(1) is called. Since 1 ≠ 0, it computes 1 * Factorial(0).
  5. Factorial(0) is called. n=0n = 0, so it hits the base case and returns 1.

The call stack now unwinds: 6. The call to Factorial(1) receives 1 and returns 1∗1=11 * 1 = 1. 7. The call to Factorial(2) receives 1 and returns 2∗1=22 * 1 = 2. 8. The call to Factorial(3) receives 2 and returns 3∗2=63 * 2 = 6. 9. The original call to Factorial(4) receives 6 and returns 4∗6=244 * 6 = 24.

Final Answer: 24

Worked example 2

Write a recursive function Power(Base, Exponent) that calculates $Base^{Exponent}$, assuming the exponent is a non-negative integer. Trace the execution for Power(3, 4).

Show solution outline
FUNCTION Power(Base : REAL, Exponent : INTEGER) RETURNS REAL
  IF Exponent = 0 THEN
    RETURN 1  // Base Case: Any number to the power of 0 is 1
  ELSE
    RETURN Base * Power(Base, Exponent - 1) // Recursive Step
  ENDIF
ENDFUNCTION

Execution Trace for Power(3, 4):

  1. Power(3, 4) calls 3 * Power(3, 3)
  2. Power(3, 3) calls 3 * Power(3, 2)
  3. Power(3, 2) calls 3 * Power(3, 1)
  4. Power(3, 1) calls 3 * Power(3, 0)
  5. Power(3, 0) is called. It hits the base case and returns 1.

Unwinding the stack: 6. The call to Power(3, 1) receives 1 and returns 3∗1=33 * 1 = 3. 7. The call to Power(3, 2) receives 3 and returns 3∗3=93 * 3 = 9. 8. The call to Power(3, 3) receives 9 and returns 3∗9=273 * 9 = 27. 9. The original call to Power(3, 4) receives 27 and returns 3∗27=813 * 27 = 81.

Final Answer: 81

Mark a 9618 question on this topicFull lessonOpen in course studio