ハノイの塔（再帰）

function hanoi(n, from, to, aux) {
    // ベースケース：1枚の円盤なら直接移動
    if (n === 1) {
        console.log(`円盤1を${from}から${to}に移動`);
        return;
    }
    
    // ステップ1：上のn-1枚を補助杭に移動
    hanoi(n - 1, from, aux, to);
    
    // ステップ2：最下段の円盤を目標杭に移動
    console.log(`円盤${n}を${from}から${to}に移動`);
    
    // ステップ3：補助杭のn-1枚を目標杭に移動
    hanoi(n - 1, aux, to, from);
}

// 使用例：3枚の円盤を杭Aから杭Cに移動
hanoi(3, 'A', 'C', 'B');

// 出力：
// 円盤1をAからCに移動
// 円盤2をAからBに移動
// 円盤1をCからBに移動
// 円盤3をAからCに移動
// 円盤1をBからAに移動
// 円盤2をBからCに移動
// 円盤1をAからCに移動

// 移動回数を計算する関数
function calculateMoves(n) {
    return Math.pow(2, n) - 1;
}

console.log(calculateMoves(3)); // 7
console.log(calculateMoves(10)); // 1023

// 注意：この再帰実装は O(2^n) の時間計算量
// 大きなnでは非常に時間がかかります