C++ 函数的递归实现：递归的常见用法有哪些？

递归是一种函数调用自身的技术，广泛应用于分步求解问题的场景。在 C++ 中，递归有以下常见用法：求解斐波那契数列计算阶乘计算排列组合遍历树形结构解决迷宫求解问题

C++ 函数的递归实现：探索递归在编程中的常见用法

递归是一种计算机科学技术，允许函数调用自身。它广泛应用于需要分步求解问题的场景中。本文将探讨 C++ 中递归的常见用法，并通过实战案例进行说明。

基本用法：斐波那契数列

最简单的递归用法是求斐波那契数列。此数列中的每个数都是前两个数的和，具体实现如下：

int fibonacci(int n) {
  if (n <= 1) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

Factorial 计算

求取一个数字的阶乘也是一个经典的递归应用。阶乘是将该数字与所有小于它的正整数相乘所得的结果。

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

排列组合

递归还可以用于计算排列组合。排列是按特定顺序排列对象的方案数，而组合是无需考虑顺序的排列方式。

排列：

int permutations(int n, int r) {
  if (r == 0) {
    return 1;
  } else {
    return n * permutations(n - 1, r - 1);
  }
}

组合：

int combinations(int n, int r) {
  if (r == 0 || n == r) {
    return 1;
  } else {
    return combinations(n - 1, r - 1) + combinations(n - 1, r);
  }
}

树形结构的遍历

递归广泛应用于遍历树形结构，例如树和图。

二叉树先序遍历：

void preorderTraversal(TreeNode* root) {
  if (root != nullptr) {
    std::cout << root->val;
    preorderTraversal(root->left);
    preorderTraversal(root->right);
  }
}

实战案例：迷宫求解

使用递归可以解决迷宫求解问题。递归算法通过尝试所有可能的路径，直至找到通往出口的路径。

bool solveMaze(int x, int y, int** maze) {
  if (maze[x][y] == 2) {
    return true;
  } else if (maze[x][y] == 0) {
    return false;
  } else {
    maze[x][y] = 0;
    return solveMaze(x + 1, y, maze) || 
           solveMaze(x, y + 1, maze) || 
           solveMaze(x - 1, y, maze) || 
           solveMaze(x, y - 1, maze);
  }
}