Data structures: how do I draw recursion trees?

Question

I have a question which I'm not sure how to begin. Can someone explain how to do this recursion tree? And is there anyway to do it on Java?

For the recursive method fnc(n,k) defined below, draw the recursion tree of the call fnc(3,5).

Your diagram should include the return values for all calls to method fnc(n,k).

public static int fnc(int n, int k) {
    if ( (n <= 1) || (k <= 1) ) {
        return n+k; } else {
        return fnc(n-1,k) + fnc(n,k-2);
    }
}

Does my answer help, do you need any more information? – Adam Mar 05 '15 at 20:35 — Adam, Mar 05 '15 at 20:35

score 0 · Answer 1 · edited May 23 '17 at 12:12

If I understand correctly, you just need to keep track of the level at which the recursion is and use that to control the indenting...

Single entry single exit would probably help here so only need one print statement for the return
String.format() quite handy for output multiple values
pad() method to create repeated string - see Simple way to repeat a String in java for alternatives

Example

static int fnc(int n, int k, int level) {
    System.out.println(String.format("%sfnc(%d, %d)", pad(level), n, k));
    int result;
    if ((n <= 1) || (k <= 1)) {
        result = n + k;
    } else {
        result = fnc(n - 1, k, level + 1) + fnc(n, k - 2, level + 1);
    }
    System.out.println(String.format("%s<== %d", pad(level), result));
    return result;
}

private static String pad(int level) {
    String pad = "";
    for (int i = 0; i < level; i++) {
        pad += "  ";
    }
    return pad;
}

public static void main(String[] args) {
    fnc(3, 5, 0);
}

Output

fnc(3, 5)
  fnc(2, 5)
    fnc(1, 5)
    <== 6
    fnc(2, 3)
      fnc(1, 3)
      <== 4
      fnc(2, 1)
      <== 3
    <== 7
  <== 13
  fnc(3, 3)
    fnc(2, 3)
      fnc(1, 3)
      <== 4
      fnc(2, 1)
      <== 3
    <== 7
    fnc(3, 1)
    <== 4
  <== 11
<== 24

Data structures: how do I draw recursion trees?

1 Answers1