[转载] (c#)数据结构与算法分析 --递归
时间：2010-11-04 来源：higirle
第2层
|
n=4 |
||||||
第3层
返回 10 |
返回 15
返回15
（这个表格在firefox下显示有点问题）
这时，应该把递归理顺了吧，自己可以试试用递归求阶乘，然后试着解决汉诺塔问题，google搜一下会有很多汉诺塔问题的源码。
很明显，上面那个递归是尾递归，在某些情况下，比如函数体比较庞大，有很多局部变量，则很容易引起栈溢出。有时候应该消除递归。
这就用到栈了，下面这个源码，功能和上面一样，只不过用栈来消除递归了。
1 //消除递归，使用栈代替递归
2 private int triangleStack(int n)
3 {
4 Stack<int> traingle = new Stack<int>(); //这个栈来模拟递归中的环境变量
5
6 while (n >= 1) //相当于递归中的基准了
7 {
8 traingle.Push(n); //将每次递减的值压入栈，相当于逐层调用递归
9 n = n - 1;
10 }
11
12 while (traingle.Count > 0) //这个相当于逐层跳出递归
13 {
14 n = n + traingle.Pop(); //计算
15 }
16
17 return n;
18 }
不是很难吧，主要把递归的原理理清，思路自然就明了了。
要注意的是，使用递归千万可别忘了基准情形，不然就永远递归不出来了。递归的效率有时候比较低，这样就可以用栈或循环来代替递归了。
2 private int triangleStack(int n)
3 {
4 Stack<int> traingle = new Stack<int>(); //这个栈来模拟递归中的环境变量
5
6 while (n >= 1) //相当于递归中的基准了
7 {
8 traingle.Push(n); //将每次递减的值压入栈，相当于逐层调用递归
9 n = n - 1;
10 }
11
12 while (traingle.Count > 0) //这个相当于逐层跳出递归
13 {
14 n = n + traingle.Pop(); //计算
15 }
16
17 return n;
18 }
不是很难吧，主要把递归的原理理清，思路自然就明了了。
要注意的是，使用递归千万可别忘了基准情形，不然就永远递归不出来了。递归的效率有时候比较低，这样就可以用栈或循环来代替递归了。
相关阅读 更多 +
