ContextQMD
Back to Freecodecamp

Step 42

curriculum/challenges/english/blocks/learn-recursion-by-solving-the-tower-of-hanoi-puzzle/64df353d7ae6dc148fd64f53.md

latest2.4 KB
Original Source

--description--

That's all for the iterative solution. From now on you are going to build a function that makes use of a recursive approach. Recursion is when a function calls itself. In this case, you are going to use recursion to calculate smaller versions of the same problem.

Delete the whole body of the move function except for the comment and the first print call. Leave the function declaration as is.

--hints--

You should delete the whole body of the move function except for the comment and the first print call.

js
({ test: () => assert.match(code, /print\(\s*rods\s*,\s*('|")\\n\1\s*\)\s+(?=#\sinitiate)/) })

--seed--

--seed-contents--

py
NUMBER_OF_DISKS = 4
number_of_moves = 2 ** NUMBER_OF_DISKS - 1
rods = {
    'A': list(range(NUMBER_OF_DISKS, 0, -1)),
    'B': [],
    'C': []
}

def make_allowed_move(rod1, rod2):    
    forward = False
    if not rods[rod2]:
        forward = True
    elif rods[rod1] and rods[rod1][-1] < rods[rod2][-1]:
        forward = True              
    if forward:
        print(f'Moving disk {rods[rod1][-1]} from {rod1} to {rod2}')
        rods[rod2].append(rods[rod1].pop())
    else:
        print(f'Moving disk {rods[rod2][-1]} from {rod2} to {rod1}')
        rods[rod1].append(rods[rod2].pop())
    
    # display our progress
    print(rods, '\n')

--fcc-editable-region--
def move(n, source, auxiliary, target):
    # display starting configuration
    print(rods, '\n')
    for i in range(number_of_moves):
        remainder = (i + 1) % 3
        if remainder == 1:
            if n % 2 != 0:
                print(f'Move {i + 1} allowed between {source} and {target}')
                make_allowed_move(source, target)
            else:
                print(f'Move {i + 1} allowed between {source} and {auxiliary}')
                make_allowed_move(source, auxiliary)
        elif remainder == 2:
            if n % 2 != 0:
                print(f'Move {i + 1} allowed between {source} and {auxiliary}')
                make_allowed_move(source, auxiliary)
            else:
                print(f'Move {i + 1} allowed between {source} and {target}')
                make_allowed_move(source, target)
        elif remainder == 0:
            print(f'Move {i + 1} allowed between {auxiliary} and {target}')
            make_allowed_move(auxiliary, target)           
--fcc-editable-region--

# initiate call from source A to target C with auxiliary B
move(NUMBER_OF_DISKS, 'A', 'B', 'C')