Write a divide$-$and$-$conquer algorithm for the Towers of Hanoi problem. The

Towers of Hanoi problem consists of three pegs and n disks of different sizes.

The object is to move the disks that are stacked, in decreasing order of their size,

on one of the three pegs to a new peg using the third one as a temporary peg. The

problem should be solved according to the following rules: $(1)$ when a disk is

moved, it must be placed on one of the three pegs; $(2)$ only one disk may be

moved at a time, and it must be the top disk on one of the pegs; and $(3)$ a larger

disk may never be placed on top of a smaller disk.

$($a$)$ Show for your algorithm that S $($n$)=2$ n $1.($Here S $($n$)$ denotes the number of steps $($moves$),$ given an input of n disks.$)$

$($b$)$ Prove that any other algorithm takes at least as many moves as given in part $($a$).$

please write algorithm pseudocode in java