# 穷举(枚举、暴力、强力)算法
## 基本思想
在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。穷举算法效率并不高，但是适应于一些没有明显规律可循的场合。
使用穷举法思想解决实际问题，最关键的步骤是划定问题的解空间，并在该解空间中一一枚举每一个可能的解。
这里有两点需要注意：
- 解空间的划定必须保证覆盖问题的全部解
- 是解空间集合及问题的解集一定是离散的集合，也就是说集合中的元素是可列的、有限的。
穷举法用时间上的牺牲换来了解的全面性保证，因此穷举法的优势在于确保得到问题的全部解，而瓶颈在于运算效率十分低下。但是穷举法算法思想简单，易于实现，在解决一些规模不是很大的问题，使用穷举法不失为一种很好地选择，而无须太在意是够还有更快的算法。
## 经典运用：
《孙子算经》【鸡兔同笼问题】
今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？
# 递推算法
聪明一点的递推算法思想
## 基本思想
递推(recurrence)算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。从已知到未知，从小到大，这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用 循环可以实现。
- 顺推法：从已知条件出发，逐步推算出要解决问题的方法
- 逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件。
执行过程如下：
- 根据已知结果和关系，求解中间结果。
- 判定是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确的答案。
【注意】递推算法需要用户知道答案和问题之间的逻辑关系。在许多数学问题中，都有明确的计算公式可以遵循，因此可以采用递推算法来实现。
典型代表fibonacci数列递推求法（后一项等于前两项之和）f(n) = f(n-1) + f(n-2)
## 经典运用：
算盘书、斐波那契数列(兔子繁殖)（顺推法）、银行存款（逆推法）
# 迭代算法(辗转法)
## 基本思想
迭代：在计算过程中，不断用变量的旧值 递推出变量的新值。是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。
- 解决问题时总是重复利用一段程序(可以是几行代码，也可以是一个函数)
- 一直在更新这个变量值，迭代的含义
- 从一个
初始估计出发寻找一系列近似解来解决问题的数学过程
可分为：
- 精确迭代
- 近似迭代：二分法和牛顿迭代法
## 基本步骤
用迭代算法解决问题时，需要做好3个方面的工作
- 确定迭代变量：直接或间接地不断由旧值递推出新值的变量
- 建立迭代关系式：新值与旧值的公式或关系。（解决迭代问题的关系）
- 对迭代过程进行控制：确定迭代次数和迭代结束条件
- 所需的迭代次数是个确定值，可以计算出来：可以构建一个固定次数的循环来实现对迭代过程的控制；
- 所需的迭代次数无法确定：需要进一步分析出用来结束迭代过程的条件。
## 经典运用：
求平方根问题
# 递归算法
充分利用自己的递归算法思想
## 基本思想
-
递归函数：一个函数在它的函数体内调用它自身的函数调用方式，这种函数也称为
递归函数。在递归函数中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。 - 递归函数的两个要素：边界条件、递归方程
-
递归算法：一种直接或间接地调用原算法本身的一种算法。往往可以简化代码编写，提高程序的可读性。但是，不合适的递归会导致程序的执行效率变低。
- 递归过程一般通过函数或子过程实现；
- 递归算法在函数或子过程的内部，直接或间接调用自己的算法
- 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解
递归分为两个阶段:
- 递推：把复杂的问题的求解推到比原问题简单一些的问题的求解;
- 回归：当获得最简单的情况后, 逐步返回, 依次得到复杂的解.
函数的递归调用分两种情况：直接递归和间接递归。
- 直接递归：即在函数中调用函数本身。
- 间接递归：即间接地调用一个函数，如出如func_a调 用 func_b, func_b 又调用func_a。间接递归用得不多。
优点：
代码简洁、可读性好（这一点，对于初学者可能会反对）。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。
缺点：
由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能会造成栈溢出
注意：
必须有一个明确的递归结束条件(递归出口)如果递归次数过多，容易造成栈溢出。
## 经典运用：
汉诺塔问题、阶乘问题
# 迭代与递归的区别、联系
从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。
但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。
这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)，其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。 因而可以从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代。
采用递归算法需要的前提条件是，当且仅当一个存在预期的收敛（有确定的(或有限的)极限）时，才可采用递归算法，否则，就不能使用递归算法。
递归中一定有迭代、递归不一定能转为迭代举例 —— 链表定义
ElemSN* CreatLink3(int data[], int n) //递归法创建链表
{
ElemSN *p = NULL;
if(n==0) return NULL;
p = (ElemSN *)malloc(sizeof(ElemSN));
p->data = data[n-1];
p->next = CreatLink3(data, n-1);
return P;
}
递归中一定有迭代(递归函数的传入参数每次都会被递归函数处理，并赋予新值)。比如这个递归，虽然不能转换成迭代结构，但其中仍然有迭代，迭代变量为n，每次在迭代过程中被处理，其结果会作为下次迭代的初始值
## 循环
循环是程序控制结构，不是算法，不要混为一谈。
迭代与循环：迭代中，一般是用循环结构来完成迭代次数的计算。
递归与循环：一切递归问题都可以转化为循环求解。不过有些问题中，递归转换为循环实现，需要自己维护堆栈，比如汉诺塔问题
### 递归算法转为循环求解
递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。
将递归算法转换为非递归算法有两种情况：
- 一种是简单递归问题，可以直接求值，不需要回溯。使用一些变量保存中间结果，称为
直接转换法；比如尾递归(最后一句话进行递归)、单向递归(函数中只有一个递归调用地方) - 另一种是复杂递归问题，不能直接求值，需要回溯。需要使用栈保存中间结果加以实现，称为
间接转换法。
使用非递归方式实现递归问题的算法程序，不仅可以节省存储空间，而且可以极大地提高算法程序的执行效率。下面分别讨论这两种方法。
1. 直接转换法
直接转换法通常用来消除 尾递归和 单向递归，将递归结构用循环结构来替代。
尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法：
long fact(int n)
{
if(n==0) return 1;
else return n*fact(n-1);
}
当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法：
long fact(int n)
{
int s=0;
for(int i=1; i<=n;i++)
s=s*i; //用s保存中间结果
return s;
}
单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下：
int f(int n)
{
if(n == 1 || n ==0) return 1;
else return f(n-1)+f(n-2);
}
对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。例如求斐波那契数列的算法中用s1和s2保存中间的计算结果，非递归函数如下：
int f(int n)
{
int i, s;
int s1=1, s2=1;
for(i=3; i<=n; ++i){
s=s1+s2;
s2=s1;// 保存f(n-2)的值
s1=s;//保存f(n-1)的值
}
return s;
}
2. 间接转换法
该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下：
将初始状态s0进栈
while(栈不为空){
退栈，将栈顶元素赋给s;
if(s是要找的结果) 返回;
else{
寻找到s的相关状态s1;
将s1进栈
}
}
间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现(参考数据结构中树的递归、非递归(迭代)遍历)、图的深度优先遍历算法的非递归实现等等。
尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。编译器会自动把尾递归优化为循环
