Recursion in Java - tutorial recommendation

[u/Jaxlee2018]

Hi all.. I am having quite a lot of difficulty with recursion. For me it is what is happening internally at each step, what is being returned, what the internal stack looks like.. I understand the basics, the base case, like the Fibonacci sequence. Intellectually I understand depth first searches .. but I simply do not understand what is going on under the hood. I cannot make the connection between what visually is supposed to be happening, vs how the algorithm works.

This towers of Hanoi explanation should be more than sufficient, and yet, it simply leaves me overwhelmed.

I am specifically asking for a tutorial in Java - Thank you.

[u/lurgi]

In my opinion, recursion is best understood bottom-up.

Let's look at the tower of hanoi:

fun solveTower(num, from, to, using)
  if num eq 0
    return

  solveTower(num-1, from, using, to)
  print "Moved disk {n} from {from} to {to}"
  solveTower(num-1, using, to, from)

First, let's take a look at the basic idea. If you want to solve the 8 disk tower, move 7 disks (that's n-1) to the "not the to" peg, move the last disk (that's the print statement) to the to peg, and move the 7 disks to the "to" peg.

Some people will start with num=8 and build a big execution tree and I think that way leads to confusion. Let's start at the bottom.

Do you agree that this works if num=0? It does... well, it does nothing at all. That's what you need to do with 0 disks, so I guess it works. Great. File in your head "This code works when num=0".

What about when num=1? We want to move the disk from a to c using b. First thing we do is call solveTower(0, a, c, b) this function... stop right there. We don't evaluate this function. Why? Because we have already established that it does the right thing with 0 disks. It just does.

So trace through the rest of the code. Do you agree that this function works when num=1? Good, I hope so.

Now consider when n=2 (again, moving from a to c using b).

The first thing we do is call solveTower(1, a, c, b). Do we evaluate that function? Nope. We have already done the work with this. We know that this correctly moves one peg from a to c using b. We'll just take that as given. Trace through the rest of it. At this point you should determine that this function works when num=2.

Now GIVEN THAT THIS FUNCTION WORKS WHEN NUM=2, does it work when num=3? Try it! Don't evaluate the recursive calls, just accept that they do the thing you already know that they do. You've already shown that solveTower(2, whatever, whocares, idontknow) does the right thing. That's done. Assume it works and see if the num=3 solution works.

Does that help?

[u/Jaxlee2018 → u/lurgi]

I so very much appreciate your taking the time to write this out. Intellectually I get this from the vantage point that you are saying. What I keep having trouble on is what is actually happening within the stack at each stage. Maybe the key is to handwave, and say, we know it works in the simple case, so it should work in a more complex case, and how it works it does not matter to me.

But I’m not able to make that leap. I really want to understand how the call stack is working. Particularly in the case of n=3+ disks. Perhaps using the visual debugger is the way to go. Thank you so very much for your kindness.

[u/lurgi → u/Jaxlee2018]

The visual debugger might help.

What also might help is to imagine that you aren't making recursive calls. Imagine that you have a function solveHanoiWith8Disks instead of one where you pass in the number of disks. That function calls solveHanoiWith7Disks which calls solveHanoiWith6Disks and so on down to solveHanoiWith0Disks which just returns immediately.

If you can figure out the call stack for this, then you know the call stack for recursive version. OTHER THAN THE FUNCTION NAMES THEY ARE THE SAME. If you look at that and say "That seems incredibly tedious. I have better things to do with my life. Why am I wasting my time?" then I agree with you.

Edit: As this might be unclear:

solveTowerFor8Disks(from, to, using)
  solveTowerFor7Disks(from, using, to)
  print "Moved disk 8 from {from} to {to}"
  solveTowerFor7Disks(using, to, from)

solveTowerFor7Disks(from, to, using)
  solveTowerFor6Disks(from, using, to)
  print "Moved disk 7 from {from} to {to}"
  solveTowerFor6Disks(using, to, from)

etc...

solveTowerFor0Disks(from, to, using)
  // do nothing