一列数的规则如下: 1、1、2、3、5、8、13、21、34…… 求第 30 位数是多少，用递归算法实现答：
public class MainClass
{
public static void Main()
{
Console.WriteLine(Foo(30));
}
public static int Foo(int i)
{
if (i <= 0)
return 0;
else if(i > 0 && i <= 2)
return 1;
else return Foo(i -1) + Foo(i – 2);
}
}
或者：
public int GetNumberAtPos(int pos)
{
if(pos==0||pos==1)
{
return 1;
}
int res = GetNumberAtPos(pos – 1) + GetNumberAtPos(pos – 2);
return res;
}
或者：
static int Fn1(int n)
{
if (n <= 0)
{
throw new ArgumentOutOfRangeException();
}
int a = 1;
int b = 1;
int c = 1;
for (int i = 3; i <= n; i++)
{
c = checked(a + b);
a = b;
b = c;
}
return c;
}
不用递归：
static void Main(string[] args)
{
int[] num=new int[30];
num[0]=1;
num[1]=1;
int first=num[0];
int second=num[1];
for (int i = 2; i < num.Length; i++)
{
num[i] = first + second;
first = second;
second = num[i];
}
Console.WriteLine(num[29]);
Console.ReadLine();
}
什么是递归函数 / 方法?
任何一个方法既可以调用其他方法又可以调用自己, 而当这个方法调用自己时, 我们就叫它递归函数或者递归方法!
通常递归有两个特点:
1. 递归方法一直会调用自己直到某些条件满足, 也就是说一定要有出口;
2. 递归方法会有一些参数, 而它会把这些新的参数值传递给自己;(自己调自己);
递归问题要满足三个条件：
一个问题可以分解成多个子问题的解；子问题就是规模更小的问题（逻辑不变）这些被分解的子问题，除了规模不一样之外，解决思路一样存在条件来终止递归；这个好理解，因为自己调用自己总不能无线循环下去，所以必须有终止条件。
递归解决方案对于复杂的开发来说很方便，而且十分强大，但由于频繁使用调用栈（call stack）可能会引起性能问题（有些时候性能极差）。
递归通常用于: ①. 阶乘 ②. 斐波拉切数列;
1. 阶乘
阶乘 (!) 是小于某个数的所有正整数的乘积; 注意:0 既不是正整数, 又不是负整数;0 是整数; 你知道的,n 的阶乘实际上就是 n - 1 的阶乘乘以 n, 且 n >0; 它可以表示成 Factorial(n)=Factorial(n-1)*n; 这是方法的返回值, 但我们需要一个条件, 也就是出口 (注意: 递归一定要有出口) 如果 n = 0 则返回 1.
public long Fac(int n)
{
if (n == 0)
return 1;
return n * Fac(n – 1);
}
不用递归：
public long Fac(int n)
{
if (n == 0)
return 1;
long value = 1;
for (int i = n; i > 0; i–)
{
value *= i;
}
return value;
}
C# 递归算法计算阶乘的方法
2.(Fibonacci)斐波拉切数列:
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（LeonardodaFibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1,F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..
这个数列从第 3 项开始，每一项都等于前两项之和。
斐波那契数列算法的三种 C# 实现及时间复杂度分析