Question

The following function int solve() is a part of some class. Assume ‘m’ and ‘n’ are positive integers. Answer the question given below with dry run/working.

int solve(int m, int n)
  {
    int k=1;
    if(m<0)
      return −k;
    else if(m==0)
      return m;
    else
      return k+(solve(m−n, n+2));
}

What will the function solve() return if:

1. m = 16, n = 1
2. m = 9, n = 1

Answer 1

The function first initialises k = 1.

If m < 0, it returns −1

If m = = 0, it returns 0.

Otherwise, it recursively calls itself with new values m − n and n + 21 as the result.

(1) m = 16, n = 1

solve (16, 1)
→ Calls solve (16 – 1, 1 + 2) = solve (15, 3), returns 1 + solve (15, 3)

solve (15, 3)
→ Calls solve (15 − 3, 3 + 2) = solve (12, 5), returns 1 + solve (12, 5)

solve (12, 5)
→ Calls solve (12 – 5, 5 + 2) = solve (7, 7), returns 1 + solve (7, 7)

solve (7, 7)
→ Calls solve (7 − 7, 7 + 2) = solve (0, 9), returns 1 + solve (0, 9)

solve (0, 9)
→ Returns 0 (base case)

After backtracking and summing up 1 + 1 + 1 + 1 = 4

(2) m = 9, n = 1

solve (9, 1)
→ Calls solve (9 – 1, 1 + 2) = solve (8, 3), returns 1 + solve (8, 3)

solve (8, 3)
→ Calls solve (8 – 3, 3 + 2) = solve (5, 5), returns 1 + solve (5, 5)

solve (5, 5)
→ Calls solve (5 – 5, 5 + 2) = solve (0, 7), returns 1 + solve (0, 7)

solve (0, 7)
→ Returns 0 (base case)

Backtracking and summing up: 1 + 1 + 1 + 0 = 3