C++递归上机实例实现大全

  ​递归是编程中一种强大的技术，它通过函数调用自身来解决问题。以下是C++中常见的递归实现实例，涵盖了数学计算、数据结构操作、排序算法等多个方面。

1. 数学计算递归

1.1 阶乘计算

#include <iostream>
using namespace std;

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

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num);
    return 0;
}

1.2 斐波那契数列

#include <iostream>
using namespace std;

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

int main() {
    int num = 10;
    cout << "Fibonacci(" << num << ") = " << fibonacci(num);
    return 0;
}

1.3 幂运算

#include <iostream>
using namespace std;

double power(double base, int exp) {
    if (exp == 0) return 1;
    if (exp < 0) return 1 / power(base, -exp);
    return base * power(base, exp - 1);
}

int main() {
    cout << "2^5 = " << power(2, 5) << endl;
    cout << "3^-2 = " << power(3, -2);
    return 0;
}

1.4 最大公约数（GCD）

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int a = 48, b = 18;
    cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
    return 0;
}

2. 数组操作递归

2.1 数组求和

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum of array elements: " << arraySum(arr, size);
    return 0;
}

2.2 数组最大值

#include <iostream>
#include <climits>
using namespace std;

int findMax(int arr[], int size) {
    if (size == 1) return arr[0];
    return max(arr[size - 1], findMax(arr, size - 1));
}

int main() {
    int arr[] = {12, 34, 45, 9, 8, 90, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum element is " << findMax(arr, size);
    return 0;
}

2.3 数组反转

#include <iostream>
using namespace std;

void reverseArray(int arr[], int start, int end) {
    if (start >= end) return;
    swap(arr[start], arr[end]);
    reverseArray(arr, start + 1, end - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    
    reverseArray(arr, 0, size - 1);
    
    cout << "\nReversed array: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    
    return 0;
}

3. 字符串操作递归

3.1 字符串反转

#include <iostream>
#include <string>
using namespace std;

void reverseString(string &s, int left, int right) {
    if (left >= right) return;
    swap(s[left], s[right]);
    reverseString(s, left + 1, right - 1);
}

int main() {
    string str = "Hello, World!";
    cout << "Original string: " << str << endl;
    reverseString(str, 0, str.length() - 1);
    cout << "Reversed string: " << str;
    return 0;
}

3.2 检查回文字符串

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(string s, int left, int right) {
    if (left >= right) return true;
    if (s[left] != s[right]) return false;
    return isPalindrome(s, left + 1, right - 1);
}

int main() {
    string str = "madam";
    if (isPalindrome(str, 0, str.length() - 1))
        cout << str << " is a palindrome";
    else
        cout << str << " is not a palindrome";
    return 0;
}

4. 排序算法递归

4.1 快速排序

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, size - 1);
    
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    
    return 0;
}

4.2 归并排序

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    mergeSort(arr, 0, size - 1);
    
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    
    return 0;
}

5. 数据结构递归

5.1 二叉树遍历

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

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

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

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    cout << "Inorder traversal: ";
    inorderTraversal(root);
    
    cout << "\nPreorder traversal: ";
    preorderTraversal(root);
    
    cout << "\nPostorder traversal: ";
    postorderTraversal(root);
    
    return 0;
}

5.2 二叉树高度计算

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    
    cout << "Height of tree: " << treeHeight(root);
    return 0;
}

5.3 链表反转

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

Node* reverseList(Node* head) {
    if (head == nullptr || head->next == nullptr) return head;
    
    Node* rest = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    
    return rest;
}

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    
    cout << "Original list: ";
    printList(head);
    
    head = reverseList(head);
    
    cout << "Reversed list: ";
    printList(head);
    
    return 0;
}

6. 其他经典递归问题

6.1 汉诺塔问题

#include <iostream>
using namespace std;

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << endl;
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    int n = 3; // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
    return 0;
}

6.2 组合数计算（n选k）

#include <iostream>
using namespace std;

int combination(int n, int k) {
    if (k == 0 || k == n) return 1;
    return combination(n - 1, k - 1) + combination(n - 1, k);
}

int main() {
    int n = 5, k = 2;
    cout << "C(" << n << ", " << k << ") = " << combination(n, k);
    return 0;
}

6.3 全排列生成

#include <iostream>
#include <vector>
using namespace std;

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]);
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result;
    
    permute(nums, 0, result);
    
    cout << "All permutations:\n";
    for (auto& p : result) {
        for (int num : p) cout << num << " ";
        cout << endl;
    }
    
    return 0;
}

6.4 子集生成

#include <iostream>
#include <vector>
using namespace std;

void generateSubsets(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
    if (index == nums.size()) {
        result.push_back(current);
        return;
    }
    
    // Exclude current element
    generateSubsets(nums, index + 1, current, result);
    
    // Include current element
    current.push_back(nums[index]);
    generateSubsets(nums, index + 1, current, result);
    current.pop_back();
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result;
    vector<int> current;
    
    generateSubsets(nums, 0, current, result);
    
    cout << "All subsets:\n";
    for (auto& subset : result) {
        for (int num : subset) cout << num << " ";
        cout << endl;
    }
    
    return 0;
}

  ​这些递归实例涵盖了C++编程中常见的递归应用场景，从基础的数学计算到复杂的数据结构操作和算法实现。通过理解和练习这些例子，可以更好地掌握递归编程的思想和技术。