7、递归算法详解

#include <iostream>

using namespace std;

int fibonacci(int n) {
    // 基本情况：当 n 等于 0 或 1 时，斐波那契数列为 n
    if (n == 0 || n == 1) {
        return n;
    }

    // 递归调用：问题规模减小，调用自身来计算前两个数的和
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 6;
    int result = fibonacci(n);
    cout << "斐波那契数列第 " << n << " 个值为 " << result << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int arraySum(vector<int>& arr, int n) {
    // 基本情况：当数组为空时，总和为0
    if (n == 0) {
        return 0;
    }

    // 递归调用：将最后一个元素与前面元素的总和相加
    return arr[n - 1] + arraySum(arr, n - 1);
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int sum = arraySum(arr, arr.size());
    cout << "数组元素的总和为：" << sum << endl;

    return 0;
}

#include <iostream>

using namespace std;

int factorial(int n, int result = 1) {
    // 基本情况：当 n 等于 0 或 1 时，返回结果
    if (n == 0 || n == 1) {
        return result;
    }

    // 递归调用：更新结果并继续递归
    return factorial(n - 1, result * n);
}

int main() {
    int n = 5;
    int result = factorial(n);
    cout << "阶乘 " << n << "! = " << result << endl;

    return 0;
}

#include <iostream>
#include <string>

using namespace std;

bool isPalindrome(string str) {
    // 基本情况：当字符串长度小于等于1时，认为是回文字符串
    if (str.length() <= 1) {
        return true;
    }

    // 递归调用：如果首尾字符相同，则判断中间子串是否是回文字符串
    if (str[0] == str[str.length() - 1]) {
        return isPalindrome(str.substr(1, str.length() - 2));
    }

    return false;
}

int main() {
    string str = "madam";
    bool palindrome = isPalindrome(str);
    cout << "字符串 " << str << " 是否是回文字符串：" << (palindrome ? "是" : "不是") << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

void reverse(vector<int>& nums, int start, int end) {
    // 基本情况：当开始索引大于等于结束索引时，不需要反转
    if (start >= end) {
        return;
    }

    // 递归调用：交换开始和结束索引处的元素，并继续递归
    swap(nums[start], nums[end]);
    reverse(nums, start + 1, end - 1);
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    reverse(nums, 0, nums.size() - 1);

    cout << "反转后的列表：";
    for (const auto& num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>

using namespace std;

void hanoi(int n, char from, char to, char aux) {
    // 基本情况：只有一个盘子时，直接移动到目标柱子
    if (n == 1) {
        cout << "移动盘子 " << n << " 从柱子 " << from << " 到柱子 " << to << endl;
        return;
    }

    // 递归调用：先将上方的 n-1 个盘子移动到辅助柱子，再将最后一个盘子移动到目标柱子，最后将 n-1 个盘子从辅助柱子移动到目标柱子
    hanoi(n - 1, from, aux, to);
    cout << "移动盘子 " << n << " 从柱子 " << from << " 到柱子 " << to << endl;
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3;
    hanoi(n, 'A', 'C', 'B');

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int search(vector<int>& nums, int target, int index) {
    // 基本情况：当数组所有元素都被搜索过后，说明不存在目标值，返回 -1
    if (index >= nums.size()) {
        return -1;
    }

    // 递归调用：如果当前元素等于目标值，则返回索引，否则继续搜索下一个元素
    if (nums[index] == target) {
        return index;
    } else {
        return search(nums, target, index + 1);
    }
}

int main() {
    vector<int> nums = {4, 2, 6, 8, 3};
    int target = 6;
    int index = search(nums, target, 0);
    if (index != -1) {
        cout << "目标值 " << target << " 的索引是：" << index << endl;
    } else {
        cout << "目标值 " << target << " 不存在于数组中" << endl;
    }

    return 0;
}

#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

void preorderTraversal(TreeNode* node) {
    if (node == nullptr) {
        return;
    }

    cout << node->val << " ";  // 访问当前节点

    preorderTraversal(node->left);   // 递归遍历左子树
    preorderTraversal(node->right);  // 递归遍历右子树
}

int main() {
    // 构建一个二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "二叉树前序遍历结果：";
    preorderTraversal(root);
    cout << endl;

    // 释放内存
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

#include <iostream>
#include <vector>
#include <set>

using namespace std;

void dfs(vector<set<int>>& graph, int node, vector<bool>& visited) {
    visited[node] = true;
    cout << "访问节点: " << node << endl;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

int main() {
    int numNodes = 7;
    vector<set<int>> graph(numNodes);

    // 构建一个无向图
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5, 6};
    graph[3] = {1};
    graph[4] = {1};
    graph[5] = {2};
    graph[6] = {2};

    vector<bool> visited(numNodes, false);
    dfs(graph, 0, visited);

    return 0;
}

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void generateParenthesisHelper(int left, int right, string current, vector<string>& result) {
    if (left == 0 && right == 0) {
        result.push_back(current);  // 基本情况：左右括号都用完了，将当前组合添加到结果中
        return;
    }

    if (left > 0) {
        generateParenthesisHelper(left - 1, right, current + "(", result);  // 递归调用：放置左括号
    }
    if (right > left) {
        generateParenthesisHelper(left, right - 1, current + ")", result);  // 递归调用：放置右括号（需要与前面的左括号匹配）
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    generateParenthesisHelper(n, n, "", result);
    return result;
}

int main() {
    int n = 3;
    vector<string> combinations = generateParenthesis(n);
    cout << "括号生成问题的所有有效组合：" << endl;
    for (const auto& combination : combinations) {
        cout << combination << endl;
    }

    return 0;
}