CODEWITHSUNDEEP
javarecursion
David
David

Reputation: 25

How to trace through basic recursive code in java

I'm new to recursion and don't understand how it works.

This was a classwork problem that had the answer 18, but I don't understand how. From what I know, this should return 6 + 5 + 4 + 3 (3 + m-1 on the recursive line)?

Are the subtraction signs not indicative of subtraction? (assuming that m = 5)

public int test(int m)
{
   int value;
   if (m == 0)
      value = 3;
   else
      value = test(m - 1) + 3;
   return value;
}

Upvotes: 1

Views: 61

Answers (2)

dreamcrash
dreamcrash

Reputation: 51453

6 + 5 + 4 + 3 (3 + m-1 on the recursive line)? Are the subtraction signs not indicative of subtraction?

No the +3 will happen for every one of the recursive calls, actually what your function is doing is given the value of (m times 3) + 3.

So for m=5 the recursive calls will be like:

Is m = 0 ? No so let us called recursively:

  1. test(4) + 3
  2. m = 4; then test(3) + 3 + 3
  3. m = 3; then test(2) + 3 + 3 + 3
  4. m = 2; then test(1) + 3 + 3 + 3 + 3
  5. m = 1; then test(0) + 3 + 3 + 3 + 3 + 3
  6. m = 0; then exit with 3 + 3 + 3 + 3 + 3 + 3

Hence, for m=5 you get 18.

A side-note you can use the ternary operator to simplify your method to:

static public int test(int m) {
    return (m == 0) ? 3 : test(m - 1) + 3;
}

Upvotes: 3

tevemadar
tevemadar

Reputation: 13195

For visualizing what happens, scatter the code with messages:

public int test(int m)
{
   System.out.println("entering test("+m+")");
   int value;
   if (m == 0)
      value = 3;
   else
      value = test(m - 1) + 3;
   System.out.println("returning "+value+" from test("+m+")");
   return value;
}

Of course this is just the minimal program, you could also show which branch of the if was taken, m-1, and so on.

JavaScript equivalent, so it can run here in the browser:

function test(m) {
  console.log("entering test(" + m + ")");
  var value;
  if (m == 0)
    value = 3;
  else
    value = test(m - 1) + 3;
  console.log("returning " + value + " from test(" + m + ")");
  return value;
}

console.log("result: "+test(3));

On the longer run it is a good idea to learn using the debugger of the environment you are using. Among other things, debuggers can step through code line-by-line.

Upvotes: 1

Related Questions