Recursive implementation of C++ functions: What are the common uses of recursion?

Recursion is a technique in which a function calls itself, and is widely used in scenarios where problems are solved step by step. In C, recursion has the following common uses: Solving Fibonacci numbers Calculating factorials Calculating permutations and combinations Traversing tree structures Solving maze solving problems

Recursive implementation of C functions: Explore common uses of recursion in programming

Recursion is a computer science technique that allows a function to call itself. It is widely used in scenarios that require step-by-step problem solving. This article will explore common uses of recursion in C and illustrate it through practical examples.

Basic usage: Fibonacci sequence

The simplest recursive usage is to find the Fibonacci sequence. Each number in this sequence is the sum of the previous two numbers. The specific implementation is as follows:

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

Factorial Calculation

Finding the factorial of a number is also a classic recursive application. The factorial is the result of multiplying that number by all positive integers less than it.

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

Permutations and combinations

Recursion can also be used to calculate permutations and combinations. Arrangements are ways of arranging objects in a specific order, while combinations are ways of arranging objects without regard to order.

Arrangement:

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

Combination:

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

Traversal of tree structure

Recursion is widely used For traversing tree structures such as trees and graphs.

Binary tree pre-order traversal:

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

Practical case: Maze solving

Using recursion can solve the maze solving problem. The recursive algorithm works by trying all possible paths until it finds the path to the exit.

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

The above is the detailed content of Recursive implementation of C++ functions: What are the common uses of recursion?. For more information, please follow other related articles on the PHP Chinese website!