关于C++中的递归和回溯

返回机制应该在前，弄明白了返回机制递归才好理解
在调用一个函数的时候，编译器先把函数的参数从右自左压入栈中，然后用call指令跳至子过程地址，在跳之前会把当前代码所在的【段：偏移】地址压栈，当子过程执行完，会调用ret指令返回，ret指令和call相反当好是把栈中的【段：偏移】还原回寄存器（cs和ip），ret也就是C++的return关键字（当然，C++因为有重载机制，编译器会在压栈之前给所有的函数作签名改编，这是另一个话题），以上是返回的原理。
弄明白了返回，递归就好理解了，假设从主函数调用一个子函数，这个子函数每次都对参数进行一些处理并递归，那么进入函数体后栈的状态是：参数、返回地址；那么在函数中又调用自己，栈就变成了：参数、返回地址、参数、返回地址；当满足了递归的退出条件时，ret一次，回到前一次自调用的地址，从这个地址开始，处理参数让栈顶停在返回地址处，然后ret......如此往复，直到回到调用子函数的函数体，以上的例子类似于：
void fun(int p)
{
if(p<=1)//递归出口
return;
p--;
fun(p);
//这一步编译器实际上会pop ecx然后ret
return;
}

比如说你在面对一个二叉路口，你不知道要走哪条，你要尝试，尝试这个动作就是一个函数，你调用了这个函数。你选择先尝试左边这条，你往左边走，发现又有一个二叉路口，所以你在上一次尝试的结果中要再做一次尝试，即在函数内再调用一次函数，这就是递归。如果你发现这条路走不通，你就知道上一个二岔路你选择错了，所以你要走右边，这就是回溯。
给一个示范吧。主程序免了吧，就是输入图并调用search函数。现在有一个给定的图，我要从第1个节点走到第100个节点，问有没有路。
bool con[101][101];//邻接矩阵，已经有值了，con[a][b]==1表示从a能走到b。
void search(int loc)//我现在在loc这个点上，在做进一步打算了（先看看下面吧）
{
if(loc==100)//如果已经走到终点了
{
cout<<"OK"< exit(0);//我没必要继续做下去了，程序直接跳出
}
for(int i=1;i<=100;i++)//我面临100个点，有的能走，有的不能走，但是我都要看一遍
if(con[loc][i])//如果我能从这里走到那个点
if(i!=loc)//当然我不想又回到这个点
search(i);//那么我就先走上去看一看，再做进一步打算
return;//杯具，我在这个点走不到终点，那么我就不要走上这个点吧。由于递归的结构是个栈，所以我把这层函数干掉就直接回到上一层了。
}
这就是深度优先搜索的基本模型，你可以结合一些程序看看。当然有很多优化方式，比如记忆化搜索，你以后再看吧。
当然C++内函数有返回值功能，你可以在返回值里面返回相应的信息，以帮助上一层函数的决策。

以下是执行顺序，没有缩进的表示在f(0)中执行，缩进2个空格的是在f(1)中执行，依次类推，else 中的for循环在 f(1), f(2)中经常会因为if(!used[i])而跳过，只要注意到这一点，就很清楚了！
希望能帮到你..

首先 dep = 0 时，调用 f(0)
执行 else 中的 for 循环(i= 1)
used[1] = true;
a[0] = 1;
进入 dep = 1
执行 else 中的 for 循环(i= 2)
used[2] = true;
a[1] = 2;
进入 dep = 2
执行 else 中的 for 循环，(i=3)
used[3] = true;
a[2] = 3;
进入 dep = 3:
dep>=n，执行 if 中的 for 循环开始打印，第一次打印哦!!!!
打印结果 1, 2, 3
返回到dep = 2
used[3] = false;
由于dep=2 的 i = 3，循环结束了，返回到dep = 1
used[2] = false;
dep=1的循环 (i = 3)
used[3] = true;
a[1] = 3;
进入dep=2(循环 i = 2)
used[2] = true;
进入dep=3(打印)
打印结果1, 3, 2
返回到dep = 2
used[2] = false;
返回到 dep = 1
used[3] = false;
返回到dep = 0
used[1] = false;

执行dep=1 中 else 的 for 循环，第二次循环 i= 2
...

多看几个例子，我记得书上的回溯和递归的例子好像讲得还可以。一本书不行，去图书馆多借几本，我当时学的时候也很想不明白，看了几个书本例子才稍微有了些头绪，我的口才不行，不能比书上说得好，去好好看下课本吧

以下是执行顺序，没有缩进的表示在f(0)中执行，缩进2个空格的是在f(1)中执行，依次类推，else 中的for循环在 f(1), f(2)中经常会因为if(!used[i])而跳过，只要注意到这一点，就很清楚了！
希望能帮到你..

首先 dep = 0 时，调用 f(0)
执行 else 中的 for 循环(i= 1)
used[1] = true;
a[0] = 1;
进入 dep = 1
执行 else 中的 for 循环(i= 2)
used[2] = true;
a[1] = 2;
进入 dep = 2
执行 else 中的 for 循环，(i=3)
used[3] = true;
a[2] = 3;
进入 dep = 3:
dep>=n，执行 if 中的 for 循环开始打印，第一次打印哦!!!!
打印结果 1, 2, 3
返回到dep = 2
used[3] = false;
由于dep=2 的 i = 3，循环结束了，返回到dep = 1
used[2] = false;
dep=1的循环 (i = 3)
used[3] = true;
a[1] = 3;
进入dep=2(循环 i = 2)
used[2] = true;
进入dep=3(打印)
打印结果1, 3, 2
返回到dep = 2
used[2] = false;
返回到 dep = 1
used[3] = false;
返回到dep = 0
used[1] = false;

执行dep=1 中 else 的 for 循环，第二次循环 i= 2
...
你的串号我已经记下，采纳后我会帮你制作