C++ 関数の再帰的実装: 再帰の古典的なパズルの例?

再帰は、関数がそれ自体を呼び出して複雑な問題をサブ問題に分解することで解決できるようにするプログラミング手法です。実際のケースでは、ハノイの塔パズルの再帰的実装は次のとおりです。 1. ディスクが 1 つだけの場合は、ターゲットの塔に直接移動します。 2. 小さなディスクを補助タワーに移動します。 3. 最大のディスクをターゲット タワーに移動します。 4. 小さなディスクを補助タワーからターゲット タワーまで移動します。

#C 関数の再帰的実装: 古典的なパズルの例

再帰は、関数がそれ自体を呼び出して問題を解決できるようにするプログラミング手法です。これは、サブ問題に分割する必要がある複雑な問題に適しています。

再帰関数の構文

C では、再帰関数の構文は次のとおりです:

return_type function_name(parameter_list) {
  // 处理基线情况
  if (base_condition) {
    return base_result;
  }
  
  // 处理递归情况
  return function_name(updated_parameter_list);
}

そのうち:

• #return_type は関数によって返される型です。
• function_name は関数の名前です。
• parameter_list は、関数に渡されるパラメータのリストです。
• base_condition は再帰のベースライン条件であり、関数の再帰ループがいつ終了するかを決定します。
• base_result は、ベースライン状況が true の場合に関数によって返される結果です。
• updated_pa​​rameter_list は、関数を再帰的に呼び出すときに更新されるパラメータ リストです。

実践例: ハノイの塔

ハノイの塔は古典的な再帰パズルです。 3 つの塔があり、それぞれにディスクの数が異なります。目標は、小さいディスクが常に大きいディスクの上にあるようにしながら、最初のタワーから 3 番目のタワーまですべてのディスクを移動することです。

void hanoi(int n, char from, char to, char aux) {
  // 基线情况：只有一个圆盘时，直接移动到目标塔
  if (n == 1) {
    cout << "移动盘子 " << n << " 从塔 " << from << " 到塔 " << to << endl;
    return;
  }
  
  // 递归情况：将塔上的较小圆盘移动到辅助塔
  hanoi(n-1, from, aux, to);
  
  // 将最大的圆盘移动到目标塔
  cout << "移动盘子 " << n << " 从塔 " << from << " 到塔 " << to << endl;
  
  // 将较小的圆盘从辅助塔移动到目标塔
  hanoi(n-1, aux, to, from);
}

int main() {
  int num_disks;
  cout << "请输入圆盘数量：";
  cin >> num_disks;
  
  // 调用递归函数解决汉诺塔问题
  hanoi(num_disks, 'A', 'C', 'B');
  
  return 0;
}

出力:

请输入圆盘数量：3
移动盘子 1 从塔 A 到塔 C
移动盘子 2 从塔 A 到塔 B
移动盘子 1 从塔 C 到塔 B
移动盘子 3 从塔 A 到塔 C
移动盘子 1 从塔 B 到塔 A
移动盘子 2 从塔 B 到塔 C
移动盘子 1 从塔 A 到塔 C

以上がC++ 関数の再帰的実装: 再帰の古典的なパズルの例?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。