按照题目给的思路递归即可，复杂度约 $O(2^n)$
在处理 $n=1$ 的情况时不要忘了 return;

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
void hnt(int n,char yl,char fz,char mb){
    if(n==1){
        printf("%c To %c\n",yl,mb);
        return;
    }
    hnt(n-1,yl,mb,fz);
    printf("%c To %c\n",yl,mb);
    hnt(n-1,fz,yl,mb);
}
signed main(){
    scanf("%lld",&n);
    hnt(n,'A','B','C');
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
void fun(int n,char p1,char p2,char p3)
{
	if(n>0){
		fun(n-1,p1,p3,p2);
		cout<<p1<<" To "<<p3<<endl;
		fun(n-1,p2,p1,p3);
	}
} 
int main(){
    int n;
    cin>>n;
    fun(n,'A','B','C');
	return 0;
}