递归转循环

recursion to stack

问题：把一个递归函数转换成非递归，由于数据量导致栈溢出了。

虽然没有看懂被人写的算法，但是看懂了逻辑结构。主要难点是因为函数主题是一个while true的循环，循环体里面是很多个 if 分支，有的分支会return，有的会改变入参a，有的分支会递归调用被改变后的a并在递归结束后做其他操作也及分支判断。

思路再加一层栈不为空的循环；

入栈元素以及元素入栈时需要做的其他操作，代替完成递归后的操作；

while true 里面的return 和 break 原先是等同的，现在需要改成break，相当于只退出while true；

如果while true里面是switch case 那么case 的 return 要改成break和赋值while true 为false；

void fun(int i) {
	while (true) {
		if (a) {
			i++;
			break;// == return;
		}
		else if(b) {
			i--;
		}
		else if (c) {
			i--;
			fun(i);//recursion
			i++;//next loop
			if (i) {//other judge
				return;
			}
		}
		else {
			i++;
		}

		switch (d) {
		case 1:
			return;
			break;
		case 2:
			i++;
			break;
		case 3:
			i--;
			fun(i);//recursion
			i++;//next loop
			if (i) {//other judge
				return;
			}
			break;
		default:
			i--;
			break;
		}
	}
}


void funStack(int fisrt) {
	struct snode { int i; bool isjudge; };
	vector<snode> S;
	S.push_back(snode{ fisrt,false });
	while (!S.empty()) {
		snode t = S.back();
		S.pop_back();
		int i = t.i;
		if (t.isjudge) { //other judge
			continue;// not return 
		}
		bool whileFlag = true;
		while (whileFlag) {
			if (a) {
				i++;
				break;// == return;
			}
			else if (b) {
				i--;
			}
			else if (c) {
				i--;
				//fun(i);//recursion
				//i++;//next loop
				//if (i) {//other judge
				//	return;
				//}
				S.push_back(snode{ i++,true });//顺序和之前相反
				S.push_back(snode{ i,false });
				break;//while true
			}
			else {
				i++;
			}

			switch (d) {
			case 1:
				//return;
				whileFlag = false;//break while true
				break;
			case 2:
				i++;
				break;
			case 3:
				i--;
				//fun(i);//recursion
				//i++;//next loop
				//if (i) {//other judge
				//	return;
				//}
				S.push_back(snode{ i++,true });//顺序和之前相反
				S.push_back(snode{ i,false });
				whileFlag = false;//break while true
				break;
			default:
				i--;
				break;
			}
		}
	}
	
}