Problem C: Hanoi Tower III

Problem C: Hanoi Ⅲ
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 799 Solved: 566
Description
Hanoi （ Also known as the river tower ） The problem is a puzzle toy from an ancient Indian legend . Vatican made three diamond pillars when he created the world , Stack on a column from bottom to top in order of size 64 A golden disk . Brahman ordered Brahman to rearrange the disc from below on another pillar in order of size . And stipulate , You can't enlarge a disc on a small disc , Only one disc can be moved between the three pillars at a time .

Those intelligence questions always require people to complete the requirements in the questions with the least steps . Why the least ？ Let's have something special this time , I hope your program can meet the requirements with the most steps , And there is no repetition of any state in this process .

Please associate the Hanoi Tower knowledge you have learned .

Input
The input contains multiple sets of data tests , Each set of data has only the number of discs n( 1 <= n <= 12)

Output
For each group, the number of times the plate meets the conditions is the most

Sample Input
1
3
12
Sample Output
2
26
531440

#include <stdio.h>
int  tower(int n);

int main()
{
    
	int n; 
	while (scanf("%d",&n) != EOF)
	{
    
		printf("%d\n",tower(n));
	}
	
	return 0;
}
// Use recursion as at least , But the first plate is first A->B,A->C, So the following recursion should be the same  
int  tower(int n)
{
    
	int sum = 0;
	if (n == 1)
	{
    
		sum+=2;// Two steps for the first plate  
		return sum;
	}
	else
	{
    
		sum += tower(n-1);
		sum ++;
		sum += tower(n-1);
		sum++;
		sum += tower(n-1);
	}
	return sum;
}