Pelaksanaan rekursif fungsi C++: Bagaimana untuk menggunakan rekursi secara berkesan pada struktur data yang berbeza?

Rekursi mengendalikan struktur data dalam C++ dengan berkesan, seperti berikut: Tatasusunan: Mudah mengira nilai jumlah dan cari nilai maksimum Senarai terpaut: Cekap mengira panjang dan senarai terpaut terbalik Pokok: Kira ketinggian dan prapesanan traversal dengan pantas

C++ Pelaksanaan Rekursif Fungsi: Digunakan Secara Berkesan pada Struktur Data

Pengenalan

Rekursi ialah teknik pengaturcaraan yang berkuasa yang membolehkan fungsi memanggil dirinya sendiri. Dalam C++, rekursi boleh digunakan untuk mengendalikan pelbagai struktur data seperti tatasusunan, senarai terpaut dan pepohon. Artikel ini akan meneroka cara rekursi boleh digunakan pada struktur data yang berbeza dan memberikan beberapa contoh praktikal tentang cara menggunakan rekursi dengan berkesan.

Susun atur

• Kira jumlah elemen tatasusunan: Menggunakan rekursi, anda boleh mengira jumlah elemen tatasusunan dengan mudah:

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

• Mencari nilai maksimum boleh digunakan untuk tatasusunan cari nilai maksimum dalam tatasusunan:

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

Senarai terpaut

• Cari panjang senarai terpaut: Ulangan boleh digunakan untuk mengira panjang senarai terpaut dengan cekap:

Menggunakan rekursi, anda juga boleh membalikkan senarai terpaut dengan mudah:

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

pokok

Rekursi ialah cara biasa untuk mengira ketinggian pokok:

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

  Salin selepas log masuk
Preorder traversal:

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