关于java和c++递归调用的问题。。。
我的问题是计算围棋气数的。在C++上正常运行。移植到java后出现异常。只有部分值正确。显然是在递归上出了问题。
这个问题比http://bbs.csdn.net/topics/390162210 的要更为复杂。链接的内容只是简单的递归。
但是感觉上道理是差不多的。
个人感觉是递归调用中变量的作用域问题。得到的结果也很奇怪。代码和情况如下
C++：
#include
#include
#include
using namespace std;
int i, j, a[19][19], b[19][19];
void Srand();
int S(int i, int j);
int main() {
Srand();
cout<<endl;
for (i = 0; i<19; i++) {
for (j = 0; j<19; j++) {
b[i][j] = 1;
}};
cout<<endl;
int E[19][19];
for (int I = 0; I<19; I++) {cout<<" ";
for (int J = 0; J<19; J++) {
E[i][j]=S(I,J);
cout<<setw(2)<<E[i][j];
for (i = 0; i<19; i++) {
for (j = 0; j<19; j++) {
b[i][j] = 1;}}
}cout<<endl;
};
return 0;
}
//Srand()随机生成+展示
void Srand() {//
a[2][5]=-1;a[2][4]=1;a[3][3]=1;a[3][5]=1;a[5][3]=1;a[3][7]=1;a[3][9]=1;
a[3][4]=1;a[4][3]=-1;a[6][3]=-1;a[3][6]=-1;a[3][8]=-1;
cout << " ";
for (j = 0; j<19; j++) {
cout << setw(2) << j;
}
cout << endl;
srand((int)time(NULL));
for (i = 0; i<19; i++) {
cout << setw(2) << i;
for (j = 0; j<19; j++) {
// a[i][j] = rand() % 3 - 1;
if (a[i][j] == 0) { cout << " "; }
else if (a[i][j] == -1) { cout << "●"; }//等于-1输出实心圆圈
else if (a[i][j] == 1) { cout << "○"; }//等于1，输出空心圆圈
}
cout << setw(2) << i << endl;
}cout << " ";
for (j = 0; j<19; j++) {
cout << left << setw(2) << j;
}
};
//判断(i,j)的气数,可累加(递归)
int S(int i, int j) {
int Co = 0;
if ((a[i][j] == 1) || (a[i][j] == -1)) {//是黑白棋子才能判断
if (i == 0 || i == 18 || j == 0 || j == 18) {/*【找四个边角】*/
if (i == 0) {//第一行
if (j == 0) {//第一列（即左上角0,0点）
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { Co++; b[i][j + 1] = 0; };//右和下++
if (a[i + 1][j] == 0 && b[i+1][j] == 1) { Co++; b[i + 1][j] = 0; };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; Co += S(i, j + 1); }
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; Co += S(i + 1, j); }
}
else if (j == 18) {//第19列（即右上角）
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { Co++; b[i][j - 1] = 0; }//左j-1,
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { Co++; b[i+1][j] = 0; }//
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; Co += S(i, j - 1); }
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; Co += S(i + 1, j); }
}
else if(j>0&&j<18)
{//第一行的其他列
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { Co++; b[i][j - 1] = 0; };//左右下++
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { Co++; b[i][j + 1] = 0; };
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { Co++; b[i + 1][j] = 0; };
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; Co += S(i, j - 1); };//左右下++
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; Co += S(i, j + 1); };
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; Co += S(i + 1, j); };
}
}
else if (i == 18) {//第19行
if (j == 0) {//第1列（即左下角）
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { Co++; b[i][j + 1] = 0; };//右和上++
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { Co++; b[i - 1][j] = 0; };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; Co += S(i, j + 1); };//右和上++
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; Co += S(i - 1, j); };
}
else if (j == 18) {//第1列（即右下角）
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { Co++; b[i][j - 1] = 0; };//左和上++
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { Co++; b[i - 1][j] = 0; };
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; Co += S(i, j - 1); };//左和上++
if (a[i - 1][j] == a[i][j] && b[i - 1][j ] == 1) { b[i - 1][j] = 0; Co += S(i - 1, j); };
}
else if(j>0&&j<18){//i-1为上一行，j+1，j-1为右侧一列和左侧一列。
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { Co++; b[i - 1][j] = 0; };
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { Co++; b[i][j + 1] = 0; };
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { Co++; b[i][j - 1] = 0; }
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; Co += S(i - 1, j); };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; Co += S(i, j + 1); };//左和上++
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; Co += S(i, j - 1); };
};
}
if (j == 0) {//第1列
if (i>0 && i<18) {//非角落，仅边
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { Co++; b[i - 1][j] = 0; };//上一行
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { Co++; b[i + 1][j] = 0; };//下一行
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { Co++; b[i][j + 1] = 0; }//右一列
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; Co += S(i - 1, j); };
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; Co += S(i + 1, j); };//左和上++
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; Co += S(i, j + 1); };
};
}
if (j == 18) {//第1列
if (i>0 && i<18) {//非角落，仅边
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { Co++; b[i - 1][j] = 0; };//上一行
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { Co++; b[i + 1][j] = 0; };//下一行
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { Co++; b[i][j - 1] = 0; };//左一列
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; Co += S(i - 1, j); };
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; Co += S(i + 1, j); };//左和上++
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; Co += S(i, j - 1); };
};
}
}
else {//非边角
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { Co++; b[i][j + 1] = 0; }//右和下++
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { Co++; b[i + 1][j] = 0; };
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { Co++; b[i][j - 1] = 0; };//左和上++
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { Co++; b[i - 1][j] = 0; };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; Co += S(i, j + 1); };//右和下++
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; Co += S(i + 1, j); };
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; Co += S(i, j - 1); };//左和上++
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; Co += S(i - 1, j); };
};
};
return Co;
}
C++上运行结果
Java代码：
public class st {
st(){
a[2][5]=-1;a[2][4]=1;a[3][3]=1;a[3][5]=1;a[5][3]=1;a[3][7]=1;a[3][9]=1;
a[3][4]=1;a[4][3]=-1;a[6][3]=-1;a[3][6]=-1;a[3][8]=-1;
}
int a[][]=new int[19][19];
int b[][]=new int[19][19];
int e[][]=new int[19][19];
public int S(int i, int j) {
e[i][j] = 0;
if ((a[i][j] == 1) || (a[i][j] == -1)) {//是黑白棋子才能判断
if (i == 0 || i == 18 || j == 0 || j == 18) {/*【找四个边角】*/
if (i == 0) {//第一行
if (j == 0) {//第一列（即左上角0,0点）
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { e[i][j]++; b[i][j + 1] = 0; };//右和下++
if (a[i + 1][j] == 0 && b[i+1][j] == 1) { e[i][j]++; b[i + 1][j] = 0; };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; e[i][j] =e[i][j]+ S(i, j + 1); }
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; e[i][j] =e[i][j]+ S(i + 1, j); }
}
else if (j == 18) {//第19列（即右上角）
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { e[i][j]++; b[i][j - 1] = 0; }//左j-1,
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { e[i][j]++; b[i+1][j] = 0; }//
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; e[i][j] =e[i][j]+ S(i, j - 1); }
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; e[i][j] =e[i][j]+ S(i + 1, j); }
}
else if(j>0&&j<18)
{//第一行的其他列
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { e[i][j]++; b[i][j - 1] = 0; };//左右下++
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { e[i][j]++; b[i][j + 1] = 0; };
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { e[i][j]++; b[i + 1][j] = 0; };
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; e[i][j] =e[i][j]+ S(i, j - 1); };//左右下++
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; e[i][j] =e[i][j]+ S(i, j + 1); };
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; e[i][j] =e[i][j]+ S(i + 1, j); };
}
}
else if (i == 18) {//第19行
if (j == 0) {//第1列（即左下角）
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { e[i][j]++; b[i][j + 1] = 0; };//右和上++
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { e[i][j]++; b[i - 1][j] = 0; };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; e[i][j] =e[i][j]+ S(i, j + 1); };//右和上++
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; e[i][j] =e[i][j]+ S(i - 1, j); };
}
else if (j == 18) {//第1列（即右下角）
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { e[i][j]++; b[i][j - 1] = 0; };//左和上++
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { e[i][j]++; b[i - 1][j] = 0; };
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; e[i][j] =e[i][j]+ S(i, j - 1); };//左和上++
if (a[i - 1][j] == a[i][j] && b[i - 1][j ] == 1) { b[i - 1][j] = 0; e[i][j] =e[i][j]+ S(i - 1, j); };
}
else if(j>0&&j<18){//i-1为上一行，j+1，j-1为右侧一列和左侧一列。
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { e[i][j]++; b[i - 1][j] = 0; };
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { e[i][j]++; b[i][j + 1] = 0; };
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { e[i][j]++; b[i][j - 1] = 0; }
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; e[i][j] =e[i][j]+ S(i - 1, j); };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; e[i][j] =e[i][j]+ S(i, j + 1); };//左和上++
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; e[i][j] =e[i][j]+ S(i, j - 1); };
};
}
if (j == 0) {//第1列
if (i>0 && i<18) {//非角落，仅边
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { e[i][j]++; b[i - 1][j] = 0; };//上一行
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { e[i][j]++; b[i + 1][j] = 0; };//下一行
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { e[i][j]++; b[i][j + 1] = 0; }//右一列
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; e[i][j] =e[i][j]+ S(i - 1, j); };
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; e[i][j] =e[i][j]+ S(i + 1, j); };//左和上++
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; e[i][j] =e[i][j]+ S(i, j + 1); };
};
}
if (j == 18) {//第1列
if (i>0 && i<18) {//非角落，仅边
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { e[i][j]++; b[i - 1][j] = 0; };//上一行
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { e[i][j]++; b[i + 1][j] = 0; };//下一行
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { e[i][j]++; b[i][j - 1] = 0; };//左一列
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; e[i][j] =e[i][j]+ S(i - 1, j); };
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; e[i][j] =e[i][j]+ S(i + 1, j); };//左和上++
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; e[i][j] =e[i][j]+ S(i, j - 1); };
};
}
}
else {//非边角
if (a[i][j + 1] == 0 && b[i][j + 1] == 1) { e[i][j]++; b[i][j + 1] = 0; }//右和下++
if (a[i + 1][j] == 0 && b[i + 1][j] == 1) { e[i][j]++; b[i + 1][j] = 0; };
if (a[i][j - 1] == 0 && b[i][j - 1] == 1) { e[i][j]++; b[i][j - 1] = 0; };//左和上++
if (a[i - 1][j] == 0 && b[i - 1][j] == 1) { e[i][j]++; b[i - 1][j] = 0; };
if (a[i][j + 1] == a[i][j] && b[i][j + 1] == 1) { b[i][j + 1] = 0; e[i][j] =e[i][j]+ S(i, j + 1); };//右和下++
if (a[i + 1][j] == a[i][j] && b[i + 1][j] == 1) { b[i + 1][j] = 0; e[i][j] =e[i][j]+ S(i + 1, j); };
if (a[i][j - 1] == a[i][j] && b[i][j - 1] == 1) { b[i][j - 1] = 0; e[i][j] =e[i][j]+ S(i, j - 1); };//左和上++
if (a[i - 1][j] == a[i][j] && b[i - 1][j] == 1) { b[i - 1][j] = 0; e[i][j] =e[i][j]+ S(i - 1, j); };
};
};
return e[i][j];
};
public void S1(){
for (int I = 0; I<19; I++) {
for (int J = 0; J<19; J++) {
b[I][J] = 1;
}};
for (int I1 = 0; I1<19; I1++) {
for (int J = 0; J<19; J++) {
e[I1][J]=S(I1,J);
System.out.print(e[I1][J]+" ");
}
System.out.println();
};
for (int i = 0; i<19; i++) {
for (int j = 0; j<19; j++) {
b[i][j] = 1;
}
};
}
public static void main(String[] args){
st w=new st();
for (int I = 0; I<19; I++) {
for (int J = 0; J<19; J++) {
w.S(I, J);
}
}
w.S1();
}
}
递归是一种思想，跟具体的语言的无关
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出