C语言算法问答集：深入了解递归和回溯-C++-PHP中文网

C语言算法问答集：深入了解递归和回溯

WBOY

发布： 2024-10-08 16:30:02

原创

957人浏览过

递归：一种函数自我调用的技术，针对较小的问题不断调用自身，直到满足终止条件为止。回溯：一种试错技术，从一个解或状态开始，逐步探索各种可能结果，直到找到或耗尽所有可能性。

C语言算法问答集：深入了解递归和回溯

C语言算法问答集：深入了解递归和回溯

递归

什么是递归？

立即学习“C语言免费学习笔记（深入）”；

递归是一种函数自我调用的技术。它通过不断调用自身，针对较小的问题求解，直到满足终止条件为止。

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

查看详情

实战案例：阶乘计算

int factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

登录后复制

回溯

什么是回溯？

回溯是一种试错技术。它从一个解或状态开始，逐步探索各种可能性，直到找到或耗尽所有可能结果。

实战案例：迷宫求解

struct Cell {
  int x, y;
  int visited;
};

bool solveMaze(Cell** maze, int rows, int cols) {
  Cell start = {0, 0};
  Cell end = {rows - 1, cols - 1};

  return solveMazeRecursive(&maze, &start, &end);
}

bool solveMazeRecursive(Cell** maze, Cell* current, Cell* end) {
  if (current->x == end->x && current->y == end->y) {
    return true;
  }

  // 马克当前位置为已访问
  maze[current->x][current->y].visited = true;

  // 尝试上下左右移动
  if (current->x > 0 && !maze[current->x - 1][current->y].visited) {  // 左移
    if (solveMazeRecursive(&maze, &maze[current->x - 1][current->y], &end)) {
      return true;
    }
  }
  if (current->x < rows - 1 && !maze[current->x + 1][current->y].visited) {  // 右移
    if (solveMazeRecursive(&maze, &maze[current->x + 1][current->y], &end)) {
      return true;
    }
  }
  if (current->y > 0 && !maze[current->x][current->y - 1].visited) {  // 上移
    if (solveMazeRecursive(&maze, &maze[current->x][current->y - 1], &end)) {
      return true;
    }
  }
  if (current->y < cols - 1 && !maze[current->x][current->y + 1].visited) {  // 下移
    if (solveMazeRecursive(&maze, &maze[current->x][current->y + 1], &end)) {
      return true;
    }
  }

  // 没有找到路径，恢复当前位置为未访问
  maze[current->x][current->y].visited = false;
  return false;
}

登录后复制

以上就是C语言算法问答集：深入了解递归和回溯的详细内容，更多请关注php中文网其它相关文章！