递归

递归简单来说就是自己调用自己，需要两个条件

1）递推方法

2）递归的终止条件

递归的缺点:效率低，占内存

如果递归的层级能被预知就用递归的算法否则用普通算法。

以下列出斐波那契数列和阶乘的递归算法和非递归算法

 1         /// <summary>
 2         /// 斐波那契递归算法
 3         /// </summary>
 4         /// <param name="n"></param>
 5         /// <returns></returns>
 6         private static int FBNQ(int n)
 7         {
 8             //1,1,2
 9             //FBNQ(n)=FBNQ(n-1)+FBNQ(n-2)
10             if (n<0)
11             {
12                 throw new Exception("n必须是大于0的整数");
13             }
14             if (n==0)
15             {
16                 return 1;
17             }
18             if (n==1)
19             {
20                 return 1;
21             }
22             return FBNQ(n - 1) + FBNQ(n - 2);
23         }/// <summary>
24         /// 斐波那契的非递归算法
25         /// </summary>
26         /// <param name="n"></param>
27         /// <returns></returns>
28         private static int FBNQ2(int n)
29         {
30             if (n < 0)
31             {
32                 throw new Exception("n不能为负数");
33             }
34             if (n == 0 || n == 1)
35             {
36                 return 1;
37             }
38             //1,1,2,3,5,8,13,21,34
39             int[] nums = new int[n + 1];
40             nums[0] = 1;
41             nums[1] = 1;
42             for (int i = 2; i < n + 1; i++)
43             {
44                 nums[i] = nums[i - 1] + nums[i - 2];
45             }
46             return nums[n];//数组的长度是n+1,那么最后一个元素的索引为n
47         }
48        
49         /// <summary>
50         /// 阶乘的递归算法
51         /// </summary>
52         /// <param name="n"></param>
53         /// <returns></returns>
54         private static int Jiecheng(int n)
55         { 
56         //n!=n(n-1)!
57             if (n<0)
58             {
59                 throw new Exception("n不能为负数");
60                
61             }
62             if (n==0)
63             {
64                 return 1;
65             }
66             return n * Jiecheng(n - 1);
67         }
68         /// <summary>
69         /// 阶乘的非递归算法
70         /// </summary>
71         /// <param name="n"></param>
72         /// <returns></returns>
73         private static int Jiecheng2(int n)
74         {
75             if (n < 0)
76             {
77                 throw new Exception("n不能为负数");
78             }
79             int result = 1;
80             //5*4*3*2*1
81             for (int i = 1; i <= n; i++)
82             {
83                 result = result * i;
84             }
85             return result;
86         }

View Code