CODEWITHSUNDEEP
javarecursiontowers-of-hanoi
gator
gator

Reputation: 3533

Towers of Hanoi; recursive method means method never completes?

public class han {

    public static void main(String[] args) {
        hanoi(5, "A", "B", "C");   
    }

    private static void hanoi (int n, String from, String other, String to) {
        if (n==0){
            return;
        }
        if (n>0){
            hanoi(n-1, from, to, other); //comment
            System.out.printf("Move one disk from %s to %s \n ", from, to);
            hanoi(n-1, other, from, to); //comment
        }
    }

}

I'm learning recursion and the classic example is Towers of Hanoi. I'm kind of stumped however, with the commented lines in the above code snippet.

How does this program ever reach the 2nd commented code if the method restarts at the 1st commented code? Something like the below to illustrate:

1: some junk
2: goto 1
3: more junk

How can it ever reach 3 if 2 restarts the function? Same for the Tower of Hanoi snippet: how does it ever reach the 2nd commented code?

Upvotes: 1

Views: 312

Answers (2)

thermite
thermite

Reputation: 512

When the recursive function finishes it resumes at the same place that it was called here is a small illustration that would print only the numbers from 3-1

Recursive method

public static void printRecursive(int n)
{
    if(n ==0)
        return;
    system.out.println(n);
    print(n-1);
    //continue execution here
}

Iterative method

public static void printIterative()
{
    if(n == 0)
    {
        return;
    }
    else
    {
        system.out.println(n);
        int n2 = n-1;
        if(n2 == 0)
        {
            return
        }
        else
        {
            system.out.println(n2);
            int n3 = n2-1;
            if(n3 ==0)
            {
                return;
            }
            else
            {
                system.out.println(n3);
                int n....
                ...
                ...
            }
            //continue....
        }
        //continue exectuion from second call
    }
    //continue exection from first call
}

Basically what I've done in the second method is copy and past the successive calls to print directly inline instead of calling itself.

Recursive calls will continue running from where the recursive call was made. This can be hard to wrap your head around, but well worth the effort of understanding

Upvotes: 2

Adam Arold
Adam Arold

Reputation: 30568

It does not restart. You can imagine it as a tree which is growing new branches and leaves.

After your first call to hanoi() it calls itself again and again until it reaches the base case:

if (n==0){
    return;
}

This means that when the call at the first commented line reaches the base case in all of its branches it returns to that point and continues execution.

If there is no base case (some conditional statement which makes your function return eventually) your function will be stuck in an infinite loop.

I think that the Tower of Hanoi is albeit a classic it is rather hard to understand you should start with an easier problem like calculating elements of the fibonacci sequence or a practical algorithm: the depth first search

If you have trouble understanding recursion I can suggest The Little Schemer which is an excellent book exactly about this topic. I can hardly imagine a better and more thorough explanation than that.

Upvotes: 3

Related Questions