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

以上是C++ 函式的遞迴實作：遞迴的常用用法有哪些？的詳細內容。更多資訊請關注PHP中文網其他相關文章！