Stuck with understanding recursion

Question

For the past couple of hours, I have tried to understand why the output for this program is behaving in such a weird manner. The first part of the recursive functions makes sense to me, however, the rest I, unfortunately, find extremely confusing.

I was wondering how come that the program is going backward, and even adds to a variable that should be subtracted instead. This does not make any sense to me. I would appreciate any help, thanks.

Here is my recursive function:

public static void threeWays(int id, int n) {
    if (n >= 0) {
        System.out.println(id + "=" + n);
        threeWays(id + 1, n - 1);
        threeWays(id + 1, n - 2);
        threeWays(id + 1, n - 3);
    }
}

public static void main(String[] args) {
    threeWays(1, 4);
}

And here's the output:

1=4

2=3

3=2

4=1

5=0

4=0

3=1

4=0

3=0

2=2

3=1

4=0

3=0

2=1

3=0

My advice: Write out the tree of recursive calls on a sheet of paper. This is as much as anyone here can really do for you. — Tim Biegeleisen, Oct 28 '19 at 02:05
I have drawn the table, but I can't seem to understand what is happening in the background when the function is initially called. So, I am not really sure what to do. — Abwatts, Oct 28 '19 at 02:07
To understand recursion, you must understand recursion. The program is not going backwards, the recursion is unwinding. It may be easier to run this through a debugger and carefully step through each function call with pen and paper to understand what is happening — smac89, Oct 28 '19 at 02:09
to simplify thing just call `threeWays(id + 1, n - 1);` rather than the other two calls as well. — Scary Wombat, Oct 28 '19 at 02:14
Here is a great way to start debugging: https://onlinegdb.com/HyIKAaX9S. Fork it and start debugging the code and make sure to examine the stack. I made an example demo here https://imgur.com/a/it3zbL1 — smac89, Oct 28 '19 at 02:16
https://stackoverflow.com/questions/717725/understanding-recursion — briantaurostack7, Oct 28 '19 at 02:23
I have tried debugging the function, but there was a point where it looked like the parameter passed to the function were switched, and the function printed values going backwards. This is extremely confusing and even using a debugger, I am not sure where the numbers that are displayed on the screen came from, sadly. — Abwatts, Oct 28 '19 at 02:27

ghchoi · Answer 1 · 2019-10-28T03:26:52.823

Python3 version:

  def threeWays(f, i, n):
      if n >= 0:
          print(f, i, '=', n)
          threeWays('1st', i + 1, n - 1)
          threeWays('2nd', i + 1, n - 2)
          threeWays('3rd', i + 1, n - 3)

  threeWays('    ', 1, 4)

At the first sight, it could, could look like DFS but actually not...

When threeWays is recursively called from 2nd and 3rd threeWays, 1st or 1st and 2nd threeWay(s) is/are also called...!

threeWays('   ', 1, 4)            ->     1 = 4
  threeWays('1st', 2, 3)          -> 1st 2 = 3
    threeWays('1st', 3, 2)        -> 1st 3 = 2
      threeWays('1st', 4, 1)      -> 1st 4 = 1
        threeWays('1st', 5, 0)    -> 1st 5 = 0
          threeWays('1st', 6, -1)
        threeWays('2nd', 5, -2)
        threeWays('3rd', 5, -3)
      threeWays('2nd', 4, 0)      -> 2nd 4 = 0
      threeWays('3rd', 4, -1)
    threeWays('2nd', 3, 1)        -> 2nd 3 = 1
      threeWays('1st', 4, 0)      -> 1st 4 = 0
      threeWays('2nd', 4, -1)
      threeWays('3rd', 4, -2)
    threeWays('3rd', 3, 0)        -> 3rd 3 = 0
...

I appreciate your help! But I still can't understand how those numbers are printed in such order and how the numbers change so drastically (i.e., 1st 5 = 0 to 2nd 4 = 0). — Abwatts, Oct 28 '19 at 02:28

score 0 · Answer 2 · answered Oct 28 '19 at 02:58

You might find it more useful if you indent the output to show how deep the call stack is at each point. I replaced your print statement with System.out.println(" ".repeat(id) + n); and received the output:

The structure here is that every time a number is printed, the next level shows the three numbers below in descending order, until it gets to zero. That is exactly what your function does.

Stuck with understanding recursion

2 Answers2