递归

递归

递归是一种在程序中解决问题的强大技术，它的核心思想是通过函数调用自身来解决问题。递归通常用于解决可以被分解为更小规模的同类问题的情境

求区间最大值

int f(vector<int>& arr, int l, int r) {
	if (l == r) return arr[l];
	int mid = (l + r) / 2;
	int lmax = f(arr, l, mid);
	int rmax = f(arr, mid + 1, r);
	return max(lmax, rmax);
}

// 此过程本质是一个栈
// 返回的时候会返回到栈顶

字符串的全部子序列

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

string str;
string path;
set<string> ans;

void f1(int i) {
	if (i == str.size()) {
		ans.insert(path);	
		return;
	} else {
		// 选择当前字符
		path += str[i];
		f1(i + 1);
		// 回溯，撤销选择
		// 当path的符合要求或者枚举了选中一个字符的所有情况
		// 执行下一步骤
		path.pop_back();
		// 不选择当前字符
		f1(i + 1);
	}
}

int main() {
	cin >> str;
	f1(0);
	
	// 输出所有子序列
	for (const auto& x : ans) {
		cout << x << " ";
	}
	cout << endl;
	
	return 0;
}