Recursive implementation of C++ functions: A classic puzzle example of recursion?

Recursion is a programming technique that allows a function to call itself to solve complex problems by decomposing it into sub-problems. In a practical case, the recursive implementation of the Tower of Hanoi puzzle: 1. When there is only one disk, move directly to the target tower. 2. Move the small disc to the auxiliary tower. 3. Move the largest disk to the target tower. 4. Move the small disc from the auxiliary tower to the target tower.

#Recursive Implementation of a C Function: Classic Puzzle Example

Recursion is a programming technique that allows a function to call itself to solve a problem. This is suitable for complex problems that need to be broken down into sub-problems.

The syntax of recursive function

In C, the syntax of recursive function is as follows:

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

Among them:

• return_type is the type returned by the function.
• function_name is the name of the function.
• parameter_list is the parameter list passed to the function.
• base_condition is the baseline condition for recursion, which determines when the recursive loop of the function ends.
• base_result is the result returned by the function when the baseline situation is true.
• updated_parameter_list is the parameter list that is updated when calling the function recursively.

Practical case: Tower of Hanoi

The Tower of Hanoi is a classic recursive puzzle. It has three towers, each with a different number of discs. The goal is to move all the discs from the first tower to the third tower while ensuring that the smaller discs are always on top of the larger discs.

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;
}

Output:

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

The above is the detailed content of Recursive implementation of C++ functions: A classic puzzle example of recursion?. For more information, please follow other related articles on the PHP Chinese website!