Recursive Methods, Tracing and the Tower of Hanoi (ISC Class 12 Computer Science)

Understand Recursive Methods, Tracing and the Tower of Hanoi

static int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); }
static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
static int digitSum(int n) { if (n == 0) return 0; return n % 10 + digitSum(n / 10); }
static String bin(int n) { if (n == 0) return ""; return bin(n / 2) + (n % 2); }

Recursive Methods, Tracing and the Tower of Hanoi: key facts

Parts of a recursive method

• •Base case stops the calls
• •Recursive case calls with a smaller argument
• •No base case gives StackOverflowError

Check that every call moves towards the base case.

Standard recursive definitions

• •fact(n) = n x fact(n - 1), fact(1) = 1
• •gcd(a, b) = gcd(b, a % b), gcd(a, 0) = a
• •digitSum(n) = n % 10 + digitSum(n / 10), digitSum(0) = 0

Each definition converts directly to code.

Tower of Hanoi

• •Moves for n discs = 2^n - 1
• •3 discs need 7 moves
• •4 discs need 15
• •T(n) = 2T(n - 1) + 1

T(1) = 1.

Tracing order

• •Statements before the call run going down
• •Statements after the call run coming back
• •Frames are removed last in, first out

The call stack is LIFO.

How to answer Recursive Methods, Tracing and the Tower of Hanoi questions

1. 1Identify the base case and what it returns.
2. 2Write the first call with its arguments, then each recursive call on a new indented line until the base case.
3. 3Note any print statement and whether it is before or after the recursive call.
4. 4Work back up: substitute each returned value into the waiting expression.
5. 5Write the final value or the printed sequence exactly.
6. 6State what the method computes in one line (for example, a x b by repeated addition).

Recursive Methods, Tracing and the Tower of Hanoi in real life

The idea, met in an everyday situation. Answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Tricks to remember Recursive Methods, Tracing and the Tower of Hanoi

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Base case first

  Write the stopping line before the recursive line.

  Use it when: Writing any recursive method.

• Down then up

  Expand the calls going down, then collect the answers coming up.

  Use it when: Dry runs.

• Before or after

  Print before the call: down order. Print after the call: reverse order.

  Use it when: Output-order questions.

• Hanoi = 2 to the n, minus 1

  Double the previous count and add one: 1, 3, 7, 15, 31.

  Use it when: Counting Hanoi moves.

Recursive Methods, Tracing and the Tower of Hanoi: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

static void p(int n) {
    if (n == 0) return;
    p(n - 1);
    System.out.print(n % 2);
    p(n - 1);
}

static void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);
    System.out.println("Move disc " + n + " from " + from + " to " + to);
    hanoi(n - 1, via, to, from);
}

Where students lose marks in Recursive Methods, Tracing and the Tower of Hanoi

The slips examiners see most often, and what to write instead.

• ✗Mistake: Missing base case

  The recursion never ends.

  Wrong working

  static int f(int n) { return n * f(n - 1); }

  Right working

  static int f(int n) { if (n <= 1) return 1; return n * f(n - 1); }

  ✓Do this: Write the stopping condition first.

  Usually costs: 1 mark

• ✗Mistake: Not moving towards the base case

  An argument that does not shrink gives infinite calls.

  Wrong working

  return gcd(a, b);

  Right working

  return gcd(b, a % b);

  ✓Do this: Check the argument changes in every call.

  Usually costs: 1 mark

• ✗Mistake: Reversed output order

  A print after the recursive call runs on the way back.

  Wrong working

  For static void show(int n){ if(n==0) return; System.out.print(n+" "); show(n-1); System.out.print(n+" "); }, assuming show(3) prints only 3 2 1 and ignoring the print after the call.

  Right working

  For the same method, show(3) prints 3 2 1 1 2 3: the first print runs going down (3 2 1), and the print after the call runs coming back (1 2 3).

  ✓Do this: Mark where each print sits relative to the call.

  Usually costs: 1 mark

Practice questions on Recursive Methods, Tracing and the Tower of Hanoi

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · MCQBoard level

   Infinite recursion in Java ends with
   (a) NullPointerException (b) StackOverflowError (c) ArithmeticException (d) a compile-time error

   Hint

   The call stack runs out.

   Answer

   (b) StackOverflowError

2. Q2 · 2 marks · Short answerBoard level

   Write a recursive method to find the factorial of n. Name its base case and recursive case.

   Hint

   n! = n x (n - 1)!

   Answer

   static int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); } The base case is n <= 1, returning 1. The recursive case is n * fact(n - 1).

3. Q3 · 3 marks · Short answerHarder board level

   Dry-run mystery(4, 3) and state what the method computes:

   static int mystery(int a, int b) {
       if (b == 0) return 0;
       return a + mystery(a, b - 1);
   }

   Hint

   Expand until b is 0.

   Answer

   mystery(4, 3) = 4 + mystery(4, 2) = 4 + 4 + mystery(4, 1) = 4 + 4 + 4 + mystery(4, 0) = 12 + 0 = 12. The method computes a x b by repeated addition.

4. Q4 · 4 marks · Short answerHarder board level

   Write a recursive method to find the sum of the digits of an integer and trace it for 4729.

   Hint

   Use n % 10 and n / 10.

   Answer

   static int digitSum(int n) { if (n == 0) return 0; return n % 10 + digitSum(n / 10); } Trace: digitSum(4729) = 9 + digitSum(472) = 9 + 2 + digitSum(47) = 9 + 2 + 7 + digitSum(4) = 9 + 2 + 7 + 4 + digitSum(0) = 22.

5. Q5 · 4 marks · Case-basedHOTS / competency

   Consider the recursive binary search below on a = {2, 5, 8, 12, 16, 23, 38}:

   static int bs(int[] a, int key, int lo, int hi) {
       if (lo > hi) return -1;
       int mid = (lo + hi) / 2;
       if (a[mid] == key) return mid;
       if (a[mid] < key) return bs(a, key, mid + 1, hi);
       return bs(a, key, lo, mid - 1);
   }

   Find bs(a, 23, 0, 6) and bs(a, 6, 0, 6) with the number of calls for each, and name the base cases.

   Hint

   Write lo, hi and mid for each call.

   Answer

   bs(a, 23, 0, 6): mid = 3, a[3] = 12 < 23, so bs(4, 6); mid = 5, a[5] = 23 found: returns 5; two calls. bs(a, 6, 0, 6): mid = 3, 12 > 6, so (0, 2); mid = 1, 5 < 6, so (2, 2); mid = 2, 8 > 6, so (2, 1); lo > hi returns -1; four calls. Base cases: a[mid] == key (found) and lo > hi (absent).

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.What is a base case?Show answer

   The simplest input, answered directly without a further recursive call.

2. 2.What error does infinite recursion cause?Show answer

   StackOverflowError.

3. 3.How many moves for n discs in the Tower of Hanoi?Show answer

   2^n - 1.

4. 4.Which data structure holds the recursive calls?Show answer

   The call stack (LIFO).

5. 5.What does gcd(a, 0) return?Show answer

   a.

6. 6.When does a statement placed after the recursive call execute?Show answer

   On the way back, after the smaller call returns.

Recursive Methods, Tracing and the Tower of Hanoi: frequently asked questions