递归、回溯、DFS
循环是一种特殊的递归，可以称为不需要栈的递归，或者尾递归。
好文

例子给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。

分析：首先我们会想到用4267取余，然后除以10再区域，如此循环。但这样输出的顺序不会是7,6,2,4吗？于是我们就利用递归的堆栈结构的特性：先进后出。

public class Recursion{
	public static void main(String args[]){
		recursion(4267) ;
	}
	
	public static void recursion(int value){
		int quotient ;
		quotient = value/10 ;
		if(quotient!=0){ recursion(quotient) ;}
		System.out.println(value%10) ;
	}
}

递归是如何帮助我们以正确的顺序打印这些字符呢？下面是这个函数的工作流程。

将参数值除以10
如果quotient的值为非零，调用binary-to-ascii打印quotient当前值的各位数字
接着，打印步骤1中除法运算的余数

注意在第2个步骤中，我们需要打印的是quotient当前值的各位数字。我们所面临的问题和最初的问题完全相同，只是变量quotient的值变小了。我们用刚刚编写的函数（把整数转换为各个数字字符并打印出来）来解决这个问题。由于quotient的值越来越小，所以递归最终会终止。
　　一旦你理解了递归，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。如果你的每个步骤正确无误，你的限制条件设置正确，并且每次调用之后更接近限制条件，递归函数总是能正确的完成任务。
　　但是，为了理解递归的工作原理，你需要追踪递归调用的执行过程，所以让我们来进行这项工作。追踪一个递归函数的执行过程的关键是理解函数中所声明的变量是如何存储的。当函数被调用时，它的变量的空间是创建于运行时堆栈上的。以前调用的函数的变量扔保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。
　　当递归函数调用自身时，情况于是如此。每进行一次新的调用，都将创建一批变量，他们将掩盖递归函数前一次调用所创建的变量。当我追踪一个递归函数的执行过程时，必须把分数不同次调用的变量区分开来，以避免混淆。
　　程序中的函数有两个变量：参数value和局部变量quotient。下面的一些图显示了堆栈的状态，当前可以访问的变量位于栈顶。所有其他调用的变量饰以灰色的阴影，表示他们不能被当前正在执行的函数访问。
假定我们以4267这个值调用递归函数。当函数刚开始执行时，堆栈的内容如下图所示：

执行除法之后，堆栈的内容如下：

接着，if语句判断出quotient的值非零，所以对该函数执行递归调用。当这个函数第二次被调用之初，堆栈的内容如下：

堆栈上创建了一批新的变量，隐藏了前面的那批变量，除非当前这次递归调用返回，否则他们是不能被访问的。再次执行除法运算之后，堆栈的内容如下：

quotient的值现在为42，仍然非零，所以需要继续执行递归调用，并再创建一批变量。在执行完这次调用的出发运算之后，堆栈的内容如下：

此时，quotient的值还是非零，仍然需要执行递归调用。在执行除法运算之后，堆栈的内容如下:

不算递归调用语句本身，到目前为止所执行的语句只是除法运算以及对quotient的值进行测试。由于递归调用这些语句重复执行，所以它的效果类似循环：当quotient的值非零时，把它的值作为初始值重新开始循环。但是，递归调用将会保存一些信息（这点与循环不同），也就好是保存在堆栈中的变量值。这些信息很快就会变得非常重要。
　　现在quotient的值变成了零，递归函数便不再调用自身，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。
每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余运算，其结果是一个0到9之间的整数。把它与字符常量‘0’相加，其结果便是对应于这个数字的ASCII字符，然后把这个字符打印出来。

接着函数返回，它的变量从堆栈中销毁。接着，递归函数的前一次调用重新继续执行，她所使用的是自己的变量，他们现在位于堆栈的顶部。因为它的value值是42，所以调用putchar后打印出来的数字是2。输出42：

接着递归函数的这次调用也返回，它的变量也被销毁，此时位于堆栈顶部的是递归函数再前一次调用的变量。递归调用从这个位置继续执行，这次打印的数字是6。在这次调用返回之前，堆栈的内容如下,输出426：

现在我们已经展开了整个递归过程，并回到该函数最初的调用。这次调用打印出数字7，也就是它的value参数除10的余数。输出4267：

递归的基本原理：

　　１　每一次函数调用都会有一次返回．当程序流执行到某一级递归的结尾处时，它会转移到前一级递归继续执行．

　　２　递归函数中，位于递归调用前的语句和各级被调函数具有相同的顺序．

　　３　每一级的函数调用都有自己的局部变量．

　　４　递归函数中，位于递归调用语句后的语句的执行顺序和各个被调用函数的顺序相反．

    　　 即位于递归函数入口前的语句，由外往里执行；位于递归函数入口后面的语句，由里往外执行。

　　５　虽然每一级递归有自己的变量，但是函数代码并不会得到复制．

　　６　递归函数中必须包含可以终止递归调用的语句．

递归算法一般用于解决三类问题：

　　(1)数据的定义是按递归定义的。(Fibonacci函数)

　　(2)问题解法按递归算法实现。(回溯)

　　(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)

To Iterate,Human; to Recurse, Divine

class Solution {
public:
	void recur(int i, int n) {
		count++;
		cout << "B>";
		for (i; i < n; i++) {
			cout << "I>";
			recur(i + 1, n);
			cout << "R>";
		}
	}
	int count = 0;
};


int main()

{
	Solution solve;
	solve.recur(0, 4);
	cout << solve.count << endl;
	return 0;

}

下面我改变recur中 n 的值，来看看输出的变化：

n = 1

n = 2

n = 3

n = 4
在for循环中添加变量j

for (int j = i; j < n; j++) {
			cout << "I>";
			recur(i + 1, n);
			cout << "R>";
		}

n = 2

n = 3

n = 4

太疯狂了！ for 循环加一个变量，或者增加一层循环，程序的执行次数就大大增加…所以，阅读递归函数最容易的方法不是纠缠于它的执行过程，而是相信递归函数会顺利完成它的任务。

Leetcode Swap Nodes in Pairs

class Solution {
public:
    ListNode* swapPairs (ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* tmp = head->next;
        head->next = swapPairs (tmp->next);
        tmp->next = head;
        return tmp;
    }
};

LeetCode Pascal’s Triangle

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);
        
        for (int i = 0; i < numRows; i++) {
            res[i].resize(i + 1);
            res[i][0] = 1;
            res[i][i] = 1;
            for (int j = 1; j < i; j++) {
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
        return res;
    }
};

注意因为后面有对res 元素的操作，所以开头定义 vector<vector> 时要注意初始化。
假设numRows = 5，那么我们需要首先将vector<vector<int>>初始化为
[
[]
[]
[]
[]
[]
] 否则后面的res[i][j]等操作就是在null上的无意义操作了（似乎可以看一下stl源码剖析，进一步理解vector的迭代器）。
resize()

好文

例子 给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。