回文是指特殊的字符串，它从头到尾读与从尾到头读的内容是一致的，比如说“doggod”,无论从左到右耗时从右到左都是一样的。使用递归算法判断一个字符串是否为回文，如果是返回1，不是返回0。在主函数中输入一个字符串，并通过该递归函数进行判断，并输出结果。
#include <iostream>
#include <string>
using namespace std;
bool is_palindrome(string s, int start, int end) {
if (start >= end)
return true;
if (s[start] != s[end])
return false;
return is_palindrome(s, start + 1, end - 1);
}
int main() {
string input;
cout << "请输入一个字符串：";
cin >> input;
if (is_palindrome(input, 0, input.length() - 1))
cout << "是回文" << endl;
else
cout << "不是回文" << endl;
return 0;
}对从大到小顺序的数据进行二分查找，并要求使用递归函数实现该二分查找，如果找到则返回该数据的所在的位置，如果找不到则返回-1。在主函数中输入从大到小顺序的数据进和要查找的数据，并通过该递归函数进行查找，并输出结果
#include <iostream>
#include <vector>
using namespace std;
int binary_search_recursive(vector<int>& arr, int target, int left, int right) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] > target)
return binary_search_recursive(arr, target, mid + 1, right);
else
return binary_search_recursive(arr, target, left, mid - 1);
}
return -1;
}
int main() {
vector<int> data;
int n, target;
cout << "请输入数据个数：";
cin >> n;
cout << "请输入从大到小顺序的数据：" << endl;
for (int i = 0; i < n; ++i) {
int value;
cin >> value;
data.push_back(value);
}
cout << "请输入要查找的数据：";
cin >> target;
int result = binary_search_recursive(data, target, 0, n - 1);
if (result != -1)
cout << "数据 " << target << " 所在位置为：" << result << endl;
else
cout << "数据 " << target << " 未找到" << endl;
return 0;
}用递归算法实现归并排序，在主函数中输入一些数据，并通过该递归函数进行排序，并将排序结果输出。
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1);
vector<int> 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;
int j = 0;
int 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 merge_sort(vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
vector<int> data;
int n;
cout << "请输入数据个数：";
cin >> n;
cout << "请输入数据：" << endl;
for (int i = 0; i < n; ++i) {
int value;
cin >> value;
data.push_back(value);
}
merge_sort(data, 0, n - 1);
cout << "排序结果：" << endl;
for (int i = 0; i < n; ++i) {
cout << data[i] << " ";
}
cout << endl;
return 0;
}用递归算法实现从一组数据中找出第二大的数，并将该数进行返回，在主函数中输入一些数据，并通过调用该递归函数求出第二大的数，并将结果输出。
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> find_second_largest_helper(vector<int>& arr, int start, int end) {
if (start == end) {
return { arr[start], INT_MIN };
}
else {
int mid = start + (end - start) / 2;
auto left = find_second_largest_helper(arr, start, mid);
auto right = find_second_largest_helper(arr, mid + 1, end);
int largest = max(left.first, right.first);
int second_largest = max(min(left.first, right.first), max(left.second, right.second));
return { largest, second_largest };
}
}
int find_second_largest(vector<int>& arr) {
auto result = find_second_largest_helper(arr, 0, arr.size() - 1);
return result.second;
}
int main() {
vector<int> data;
int n;
cout << "请输入数据个数：";
cin >> n;
cout << "请输入数据：" << endl;
for (int i = 0; i < n; ++i) {
int value;
cin >> value;
data.push_back(value);
}
int second_largest = find_second_largest(data);
cout << "第二大的数是：" << second_largest << endl;
return 0;
}给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-20,11,-4,13,-5,-2)时，最大子段和为20（11,-4,13）。（使用蛮力算法和分治算法分别实现）
源程序及运行结果：
#include <iostream>
#include <vector>
using namespace std;
int max_subarray_brute_force(vector<int>& nums) {
int n = nums.size();
int max_sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
int sum = 0;
for (int k = i; k <= j; ++k) {
sum += nums[k];
}
max_sum = max(max_sum, sum);
}
}
return max_sum;
}
int main() {
vector<int> nums = { -20, 11, -4, 13, -5, -2 };
int max_sum = max_subarray_brute_force(nums);
cout << "最大子段和为: " << max_sum << endl;
return 0;
}#include <iostream>
#include <vector>
using namespace std;
int max_crossing_subarray(vector<int>& nums, int low, int mid, int high) {
int left_sum = INT_MIN;
int sum = 0;
for (int i = mid; i >= low; --i) {
sum += nums[i];
if (sum > left_sum)
left_sum = sum;
}
int right_sum = INT_MIN;
sum = 0;
for (int j = mid + 1; j <= high; ++j) {
sum += nums[j];
if (sum > right_sum)
right_sum = sum;
}
return left_sum + right_sum;
}
int max_subarray_divide_and_conquer(vector<int>& nums, int low, int high) {
if (low == high)
return nums[low];
int mid = (low + high) / 2;
int left_max = max_subarray_divide_and_conquer(nums, low, mid);
int right_max = max_subarray_divide_and_conquer(nums, mid + 1, high);
int cross_max = max_crossing_subarray(nums, low, mid, high);
return max({ left_max, right_max, cross_max });
}
int main() {
vector<int> nums = { -20, 11, -4, 13, -5, -2 };
int max_sum = max_subarray_divide_and_conquer(nums, 0, nums.size() - 1);
cout << "最大子段和为: " << max_sum << endl;
return 0;
}