CODEWITHSUNDEEP
pythonrecursion
Orsons
Orsons

Reputation: 51

Python Recursion (Tower of Hanoi)

I'm new to python and experienced a problem that ist probably really easy to solve.

def req_steps(num_disks):
    # implement this function
    if num_disks == 0:
        return 1 
    return 2 * req_steps(num_disks-1)

print("For moving {} disks, {} steps are required.".format(3, req_steps(3)))

The function should be (2^n)-1 and I can't get the -1 to work... It has to be a recursive function.

Thanks in advance.

Edit:

The ultimate formula is = (2^(num_of_disks))-1 this means, num_of_disks = 3 should give 7 which is (2*2*2-1) moves.

Upvotes: 0

Views: 433

Answers (2)

quamrana
quamrana

Reputation: 39414

It turns out the calculation is an upside down binary representation of the formula.

This code:

def req_steps(num_disks):
    if num_disks <= 1:
        return 1 
    return 2 * req_steps(num_disks - 1) + 1

for n in range(2,7):
    print(n, req_steps(n))

produces:

2 3
3 7
4 15
5 31
6 63

The base case of num_disks==1 returns 1, but the previous recursion multiplies this by two, and adds 1. So as the recursion unfolds again it is producing a binary 1 in each binary digit place according to num_disks passed in by the original caller.

Upvotes: 0

lyh543
lyh543

Reputation: 1105

You may give the final answer f(n) = 2^n-1, which is a general fomula, while the question requests you to use the recurrence formula f(n) = f(n-1) + 1 + f(n-1) when n > 1.

    def req_steps(num_disks):
        if num_disks == 1:
            return 1
        else:
            return 1 + 2 * req_steps(num_disks - 1)
    
    print("For moving {} disks, {} steps are required.".format(3, req_steps(3)))

which outputs:

For moving 3 disks, 7 steps are required.

The below recurrence fomula means when you want to move n disks from A to C (Suppose the 3 rods placing disks are named A, B and C), you can:

  1. move n-1 disks from A to B, which takes f(n-1) steps
  2. move the nth disk from A to C, which takes 1 step
  3. move the n-1 disks from B to C, which takes f(n-1) steps

Upvotes: 1

Related Questions