递归
递归通过函数自己调用自己实现。自己调用自己需要知道什么时候停止和调用逻辑，所以递归有两个要素：
- 递归结束条件
- 递归”公式”
递归的思考方法是把大问题分解成步骤相同的小问题，每次只考虑当前结点的问题，把子问题分配给下一层函数。 例如遍历二叉树，每一个递归函数只处理根结点，至于左孩子，右孩子，作为参数传递给下一层。
递归函数可以有返回值，把自己处理后的结果传递回上一层（如计算斐波那契数列或者n的阶乘）；也可以在所有递归函数中处理同一个全局变量 （如每一个函数把自己的结果放进结果List里）。递归函数一般要利用函数参数传递信息，以告诉下一层函数从什么地方开始。如遍历二叉树时， 孩子结点作为参数传递，下一层把孩子结点作为自己的根结点。
回溯是一种算法思想，可以用递归实现。回溯是一种试探，类似于穷举，但回溯有“剪枝”功能，比如求和问题。 给定7个数字，1 2 3 4 5 6 7求和等于7的组合，从小到大搜索，选择1+2+3+4 =10>7， 已经超过了7，之后的5 6 7就没必要在继续了，也就是说优化了搜索过程。
迭代
广义上，迭代就是将输出做为输入,再次进行处理。例如：
i=i+1;
把变量更新为它参与的运算的结果。
递归与迭代的转化
递归一般比较简洁，可读性强。但是函数调用时，需要在栈中分配新的帧，将返回地址，调用参数和局部变量入栈。 所以递归调用越深，占用的栈空间越多。如果层数过深，超过环境给程序分配的栈空间，会导致栈溢出。迭代一般时间效率更高。 理论上已经证明，递归都可以转化为迭代，但是只有使用栈的迭代可能转化为递归（因为递归就是使用函数调用栈来代替手动维护栈）。 在对程序开销要求不大时，建议使用递归，以保证可读性；否则转化递归为迭代。
递归函数可以分为尾递归和非尾递归函数。前者具有固定的优化“公式”，一般只用循环就可以代替，不需要用到栈；后者一般要手动维护栈来代替。 对于优化过程较为机械化的前者，自然可以让编译器帮我们优化。但是一般只有函数式编程语言对尾递归做了优化，主流语言（如Java）没有优化。 所以两者的优化方法都需要掌握。
尾递归转化为迭代
先介绍一下尾递归，尾递归函数是指函数的最后一个动作是调用函数本身的递归函数。例如 fibonacci数列实现方法一般是这样的，
int FibonacciRecur(int n) {
if (0==n) return 0;
if (1==n) return 1;
return FibonacciRecur(n-1)+FibonacciRecur(n-2);
}
不过需要注意的是这种实现方法并不是尾递归，因为尾递归的最后一个动作必须是调用自身，这里最后的动作是加法运算，所以我们要修改一下，
int FibonacciTailRecur(int n, int acc1, int acc2) {
if (0==n) return acc1;
return FibonacciTailRecur(n-1, acc2, acc1+acc2);
}
接下来进行优化，用变量更新来代替尾递归中的参数传递。
// iterative, down-top
int fib2(int n) {
int f0 = 1, f1 = 1, i;
for (i = 2; i <= n; ++i) {
int f2 = f1 + f0;
f0 = f1; f1 = f2; //在这里实现变量的更新
}
return f1;
}
注意，优化实现了“自顶向下”向“自底向上”的转化。顶就是要解决的问题（即f(n)的值），底就是初始条件（已知f(0)和f(1)的值）。 递归从大问题分解到下一层的小问题，最后达到初始条件，小问题解决，一路回溯，解决了大问题；迭代从初始条件层层向上推算结果。
非尾递归转化为迭代
以一个二叉树的先序遍历过程为例，先处理当前根节点，然后依次处理左子树和右子树。
void PreorderRecursive(Bitree root){
if (root) {
visit(root); //当前根节点
PreorderRecursive(root->leftchild); //处理左子树
PreorderRecursive(root->rightchild); //处理右子树
}
}
使用栈进行转化，如下：
void PreorderNonRecursive(Bitree root){
stack stk;
stk.push(root); //先把root送进去
while(!stk.empty()){
p = stk.top();
visit(p); //这是伪代码
stk.pop();
//如果语言里stk.pop()返回弹出的栈顶元素，上面可以写成visit(stk.pop());
if(p.rightchild) stk.push(stk.rightchild);
if(p.leftchild) stk.push(stk.leftchild);
}
}
每次处理完当前节点后将右子树和左子树先后入栈，这样先出栈的就是左子树。
