1. 递归有点像盗梦空间。。。
每做一次递归就深入一层，如果某一层递归里满足某条件要return，就return到上一层递归语句，执行它的下一行，以此类推。
如素数环问题（部分）：
void DFS(int num)
{
... ... ;
for(int j=2; j<num; j++)
{
if(!isPrime(ans[j-2]+ans[j-1])) { return; } //如果不是素数，返回继续枚举
}
for(int i=1; i <= n; i++)
{
if(circle[i]==false)
{
circle[i]=true;
ans[num]=i;
DFS(num+1); //递归枚举
circle[i]=false;
} } }
比如，num==4时，在嵌套里执行DFS（num+1），即DFS（5）；
若此时不满足素数条件要return，return到circle[i]=false；
若此时满足for循环退出条件，说明DFS（4）的递归结束，返回到DFS（4）调用处（注意此时不是返回到main函数，而是一层一层递归，一层一层深入，一层一层浅出）；
此时DFS（4）为DFS（3+1），num==3；
以此类推。
2. 解决素数环用回溯法枚举每一个值，分为两步：
第一，当第一个数位为1确定时，尝试放入第二个数，判断这两个相邻数的和是否为素数，若满足条件，再放入第三个数，以此类推（放置过的数做个标记，以防再次放置）；
第二，若当前位置无论放任何之前未被放置过的数都无法满足条件，那么回溯改变上一个数；
以上两步，恰好可以通过递归“进出”解决。
3. 代码如下：
#include <iostream>
using namespace std;
int ans[22]; //ans数组脚标代表环中对应的位置
bool circle[22]; //circle数组脚标代表当前数字，数组值代表当前数字是否放入环中
int n; //n代表输入的数，环中待排列数字总数
//n取值范围为1<n<17
bool isPrime(int x) //判断x是否是素数，是素数返回TRUE，反之返回FALSE
{
if (x<=1)
{
return false; //小于等于1的数，必然不是素数
}
int bound = (int)sqrt(x) + 1;
for (int index = 2; index < bound; index++)
{
if (x%index == 0)
{
return false;
}
}
return true;
}
void DFS(int num) //递归枚举，num表示当前进行到环中的第几个位置，从0开始
{
int i, j;
if (num>0 && ans[0]!=1) //环的第一个数必须是1
{
return;
}
for (j = 2; j <= num; j++) //当前环中已排列的相邻数字之和是否为素数
{ //j表示位置
if (!isPrime(ans[j - 2] + ans[j - 1]))
{
return; //不是素数则返回继续枚举
}
}
for (i = 1; i <= n; i++) //i表示1~n，需填入环中的数字
{
if (!circle[i])
{
circle[i] = true;
ans[num] = i;
DFS(num + 1); //列举下一个数
circle[i] = false;
}
} //当前DFS函数递归完return到上一层的DFS函数，如，由DFS（4）回到DFS（3）
//回到DFS（3）后，下一行执行circle[i]=false;
//此时的i是发现当前位置无论如何无法满足条件后，回溯改变的上一个数
if (num==n)
{
if (isPrime(ans[num-1] + ans[0])) //如果是素数，进行下一步
{
for (j = 0; j < n; j++) //index表示位置
{
cout << ans[j] << " ";
}
cout << endl;
return;
}
}
}
int main()
{
int i, j;
int cas = 0;
while (cin>>n) //n范围从1到17
{
for (int t = 0; t < 22; t++)
{
circle[t] = false;
}
memset(ans, 0, 22 * sizeof(int)); //每轮将circle数字重新初始化
cas++;
cout << "case " << cas << ":" << '\n';
if (n%2!=0)
{
cout << endl; //若n为奇数，无法形成素数环，因为奇数+奇数=偶数，会多一个奇数
}
else
{
DFS(0); //位置从0开始
}
}
return 0;
}