原文地址:http://www.codeproject.com/Articles/142292/Recursive-methods-in-Csharp& # 160;
萨因Khorshiadnia
译者:托尼曲
递归解决方案对于复杂的开发来说很方便,而且十分强大,但由于频繁使用调用栈(调用堆栈)可能会引起性能问题(有些时候性能极差)。
我们来看一看下面这个图:
调用栈图示
下面我打算介绍一些例子来帮助你更好的理解递归的风险和回报。
阶乘(!)是小于某个数的所有正整数的乘积。
0 !=1
1 !=1
2 !=2 * 1 !=2
3 !=3 * 2 !=6
…
n !=n * (n - 1) !
下面是计算阶乘的一种实现方法(没有递归):
公共长阶乘(int n)
{
如果(n==0)
返回1;
长值=https://www.yisu.com/zixun/1;
for (int i=n;我> 0;我——)
{
值*=我;
}
返回值;
}
下面是用递归的方法实现计算阶乘,与之前的代码比起来它更简洁。
公共长阶乘(int n)
{
如果(n==0)//限制条件,对该方法调用自己做了限制
返回1;
返回n *的阶乘(n - 1);
}
你知道的n的阶乘实际上是n - 1的阶乘乘以n,且n> 0。
它可以表示成! (n)=! (n - 1) * n
这是方法的返回值,但我们需要一个条件
如果n=0返回1 .
现在这个程式的逻辑应该很清楚了,这样我们就能够轻易的理解。
<强>
斐波那契数列是按以下顺序排列的数字:
0, 1, 1, 2, 3, 5, 8, 13日,21日,34岁,55岁,…
如果F <子> 0 =0并且F <子> =1那么F <子> n =F <子> n - 1 + F <子> -
下面的方法就是用来计算Fn的(没有递归,性能好)
公共长Fib (int n)
{
如果(n & lt;2）
返回n;
长[]f=new (n + 1);
f [0]=0;
f [1]=1;
for (int i=2;我& lt;=n;我+ +)
{
[我]=f (i - 1) + f (i - 2);
}
返回f [n];
}
如果我们使用递归方法,这个代码将更加简单,但性能很差。
公共长Fib (int n)
{
如果(n==0 | | n==1)//满足条件
返回n;
返回Fib (k - 2) + Fib (k - 1);
}
<强>
有时我们需要解决的问题比斐波那契数列复杂很多,例如我们要枚举所有的布尔变量的组合。换句话说,如果n=3,那么我们必须输出如下结果:
<>以前真的,真的,真的
真的,真的,假的
真的,假的,真的
真的,假的,假的
假的,真的,真的
假的,真的,假的
假的,假的,真的
假的,假的,假的
如果n很大,且不用递归是很难解决这个问题的。
公共空CompositionBooleans(字符串结果,int计数器)
{
如果(counter==0)
返回;
bool[]布尔值=new bool[2]{真,假};
for (int j=0;j & lt;2;j + +)
{
StringBuilder StringBuilder=new StringBuilder(结果);
stringBuilder.Append (string.Format(“{0}”,布尔值[j] .ToString ())) .ToString ();
如果(counter==1)
Console.WriteLine (stringBuilder.ToString ());
CompositionBooleans (stringBuilder.ToString(),反- 1);
}
}
