递归

简介

递归就是自己调用自己。
主要有两部分：递推式，终止条件。

一些简单例子：
阶乘：

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

递归结束条件是$0! = 1$，递归式是$n! = n \times (n-1)!$。
这个递归的时间复杂度是$O(n)$。

欧几里得算法：

int gcd(int x, int y) {
	if (y == 0) {
		return x;
	}
	return gcd(y, x % y);
}

递归结束条件是$\gcd(x, 0) = x$，递归式是$\gcd(x, y) = \gcd(y, x \bmod y)$
这个递归的时间复杂度是$O(\log(x) + \log(y))$。
Fibonacci数：

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

递归结束条件是$\gcd(x, 0) = x$，递归式是$\gcd(x, y) = \gcd(y, x \bmod y)$
这个递归的时间复杂度是$O(\log(x) + \log(y))$。
快速幂：

long long pow(long long x, long long n, long long p) {
	if (n == 0) {
		return 1;
	} else {
		int t = pow(x * x % p, n / 2, p);
		if (n % 2 == 1) {
			t = t * x % p;
		}
		return t;
	}
}

递归结束条件是$x^0 \bmod p = 1$，递归式是$x^{2k + b} = (x^2)^k \times x^b$
这个递归的时间复杂度是$O(\log n)$。

等比数列求和：
求$(\sum_{0 \leq i < n} x^i) \bmod p$

long long sum(long long x, long long n, long long p) {
	if (n == 0) {
		return 0;
	} else if (n % 2 == 1) {
		return (sum(x, n - 1, p) * x + 1) % p;
	} else {
		return sum(x * x % p, n / 2, p) * (x + 1) % p;
	}
}

与循环的关系

递归与循环完全等价，也就是说程序中所有的循环，均可以用递归实现。

void dfs(int i, int n) {
	if (i == n) {
		return;
	}
	cout << i << endl;
	dfs(i + 1, n);
}

这个函数可以实现输出$i, i + 1, \ldots, n - 1$。
如果调用dfs(0, n)便可输出$0, 1, \ldots, n - 1$。

递归和非递归

递归因为不需要手动维护栈，所以代码往往非常简短。
但是递归层数过多会导致爆栈，所以在一些情况下，应避免递归。

void dfs(int i) {
	cout << i << endl;
	dfs(i + 1);
}

不开O2运行这段代码，根据平台不同，可以输出的数字也不同。
不过可以近似认为输出数字的个数乘以$4$（int类型的大小）就是栈空间。
开O2运行这段代码，递归会被展开成循环，而永远不会爆栈。

但是在一些枚举子集，枚举排列，枚举组合的题目中，如果使用非递归写法

参考题目

Luogu P1706
枚举所有排列

Luogu P1157
枚举所有组合

abc165_c

P2089 烤鸡

https://www.luogu.com.cn/problem/P2089

P1657 选书

https://www.luogu.com.cn/problem/P1657

P2562 Kitty猫基因编码

https://www.luogu.com.cn/problem/P2562

P1706 全排列问题

https://www.luogu.com.cn/problem/P1706