这两个算法有部分重合，所以一起讲。
递归 \(\sf\small\color{gray}Recursion\)
递归是递归函数的灵活运用。
说到底，它是一个 \(\color{blue}\texttt{C++}\) 的一个语言特性。
在函数内部调用函数，会使得思路更加清晰明了。
观察生活，很多事情随着规模或阶段的上升而变得越来越复杂。
然而，此规模或阶段往往又和前面的规模或阶段有着联系。
找出这个联系并解决问题的算法就叫递推。
这是我在 递推 | 差分与前缀和 里写过的一句话。
找出了关系，使用数组迭代，是递归。找出了关系，用递归函数迭代，就是递归。
递归的板子不是死的。它很活，视具体递推(归)式而变。
递归函数
int f(int a)
{
return f(a);
}
这严格来说不算一个递归函数。它永远调用自己，造成 \(\sf\color{red}死递归\) 。
int f(int a)
{
return f(a-1);
}
这样呢？
的确不是重复调用自己，可是 a 可以无限小下去，依然是死递归。
怎么办呢？
int f(int a)
{
if(a==1) return 1;
return a+f(a-1);
}
这样呢？
只要 a 是大于一的，那么这个函数就不会死。
递归函数三要素
\(\boxed{\sf调用自身}\boxed{\sf状态转移}\boxed{\sf递归边界}\)
此三者缺一不可，不然函数将失去意义。
运用递归函数
这里举一些例子，方便理解。
阶乘
使用递归函数求 \(\sf n!\) 的值。
此题用循环将非常简单。可是用递归函数呢？
调用自身是当然的。
我们按照递推的思想，把定义拆开：
边界呢？
自然是 \(1!=1\) 啦！
至此，思路已经非常清晰了。上代码！
int factorial(int a)
{
if(a==1) return 1;
return a*factorial(a-1);
}
斐波那契数
1 1 2 3 5 8 ...
我们在 递推 | 差分与前缀和 已经推过它的递推式了：
\[\sf F(i)= \begin{cases} \sf F(i-1)+F(i-2)&\sf(i>2)\\ \sf 1&\sf(i=1or2) \end{cases} \]现在我们用递归实现。
int fibonacci(int a)
{
if(a==1) return 1;
if(a==2) return 2;
return fibonacci(a-1)*fibonacci(a-2);
}
至此，有一个小问题暴露了：
F(n) 已经调用过 F(n-1) 和 F(n-2) 了，F(n-1) 又调用了 F(n-2) ，不就浪费资源了吗？
既然已经调用过，那我把它记住不就好了？
斐波那契数 - 记忆化搜索
每一次调用都看看有没有算过，如果算过，就直接拿出来用，没有就记住他。
int Ans[1000];
int fibonacci(int a)
{
if(Ans[a]!=0) return Ans[a];
if(a==1) return 1;
if(a==2) return 2;
Ans[a]=fibonacci(a-1)*fibonacci(a-2);
return Ans[a];
}
算法优劣
递归肯定是没有递推优的。每一次调用函数都会新开空间，进入与返回也会花时间，递归层数一多，栈空间还可能炸。
那为什么还用递归？
如果你不知道递推层数，你怎么知道你要什么时候停下来？
而递归 if 里的东西什么都可以。
况且递归思维难度小啊。
分治 \(\sf\small\color{gray}Partition\)
分治分治，分而治之。
字面意思，把一个问题分成两个，三个甚至多个问题。
其实分治可以想递推一样，用循环解决，二分就是一种这样的例子。
还有的，就用递归函数解决吧。
运用
快速模
int FastMod(int a,int b,int k)
{
if(b==1)return a%k;
const int o=FastMod(a,b/2,k)%k;
if(b%2) return (a%k*o%k*o%k)%k;
else return (o%k*o%k)%k;
}
此处使用了 % 的性质，不熟悉的同学可以去学学 % 的性质。
区别
我认为吧，分治和递归的本质区别是，一个是由小一点的规模迭代而来，一个是由一半的，三分之一甚至四分之一的相同子问题迭代而来。
完结散花qwq
标签：return,递归,递归函数,int,分治,递推,sf From： https://www.cnblogs.com/PCwqyy/p/18290078/Recursion-Partition