Write a recursive C program to count how many moves it would take to move all disks from peg A to peg C with the restriction that A can't go to C and C can't go to A without going through B first. If you are unwilling to reply to comments please do not answer.

Bonus: Tower of Hanoi? (5 points, can be added to your final grade) The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1. 2. 3. Only one disk can be moved at a time. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. No disk may be placed on top of a smaller disk. As a smart kid as John, getting the total number of moves needed for the game is just like a breeze. But he likes to play it differently-he added one more restriction to the game 4. You cannot move the disk from the leftmost rod directly to the rightmost one. That means if you want to do it, you have to go through the middle rod: Move the disk from the leftmost rod to the middle one, then move it from the middle one to the rightmost one. However, he is confused after adding this restriction. Can you help him? Input ann ( sn s 35), indicating the number of disks you have on the leftmast rod (in ascending order of size on ane rod, the smallest at the top). Output the total number of moves needed to move all the disks from the leftmost rod to the rightmost rod Sample Input 12 Sample Output 26 531440 Hint Solve it with the methodology of recursion