Recursive implementation of C++ functions: How to use recursion effectively on different data structures?

Recursion effectively handles data structures in C, as follows: Array: Easily calculate sum values ​​and find the maximum value Linked list: Efficiently calculate length and reverse linked list Tree: Quickly calculate height and preorder traversal

Recursive implementation of C functions: effectively applied to data structures

Introduction

Recursion is a A powerful programming technique that allows functions to call themselves. In C, recursion can be used to work with various data structures such as arrays, linked lists, and trees. This article will explore how recursion can be applied to different data structures and provide some practical examples of how to use recursion effectively.

Array

• ##Calculate the sum of arrays: Using recursion, you can easily calculate the sum of array elements:

int arraySum(int arr[], int n) {
  if (n <= 0) {
    return 0;
  }
  return arr[n-1] + arraySum(arr, n-1);
}

Copy after login

• Find the maximum value of an array: Recursion can also be used to find the maximum value in an array:

int findMax(int arr[], int n) {
  if (n == 1) {
    return arr[0];
  }
  int max = findMax(arr+1, n-1);
  return max > arr[0] ? max : arr[0];
}

Copy after login

Linked list

• Find the length of the linked list: Recursion can be used to efficiently calculate the length of the linked list:

int linkedListLength(Node* head) {
  if (head == NULL) {
    return 0;
  }
  return linkedListLength(head->next) + 1;
}

Copy after login

• Reverse the linked list: Use Recursion, you can also easily reverse the linked list:

Node* reverseLinkedList(Node* head) {
  if (head == NULL || head->next == NULL) {
    return head;
  }
  Node* next = head->next;
  head->next = NULL;
  Node* reversed = reverseLinkedList(next);
  next->next = head;
  return reversed;
}

Copy after login

tree

• Calculate the height of the tree: Recursion is the calculation A common method for tree height:

int treeHeight(Node* root) {
  if (root == NULL) {
    return 0;
  }
  int leftHeight = treeHeight(root->left);
  int rightHeight = treeHeight(root->right);
  return max(leftHeight, rightHeight) + 1;
}

Copy after login

• Pre-order traversal: Recursion can be used to pre-order traverse a tree:

void preorderTraversal(Node* root) {
  if (root == NULL) {
    return;
  }
  cout << root->data << " ";
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

Copy after login

Conclusion

The above is the detailed content of Recursive implementation of C++ functions: How to use recursion effectively on different data structures?. For more information, please follow other related articles on the PHP Chinese website!