什么是递归函数/方法?
任何一个方法既可以调用其他方法又可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或者递归方法!
通常递归有两个特点:
1.递归方法一直会调用自己直到某些条件满足,也就是说一定要有出口;
2.递归方法会有一些参数,而它会把这些新的参数值传递给自己;(自己调自己);
递归通常用于: ①.阶乘 ②.斐波拉切数列;
1.阶乘
阶乘(!)是小于某个数的所有正整数的乘积;
注意:0既不是正整数,又不是负整数;0是整数;
0!=1
1!=1
2!=2*1!=2
3!=3*2!=6
4!=4*3!=24
5!=5*4!=120
...
n!=n*(n-1)!
下面是计算阶乘的一种实现方法(没有使用递归):
1 public long Factorial(int n){
2
3 if(n==0)
4
5 return 1;
6
7 long value=1;
8
9 for(int i=n;i>0;i--){
10
11 value*=i;
12
13 }
14
15 return value;
16
17 }
// 递归方法:
1 pubic long Factorial(int n){
2
3 if(n==0){
4
5 return 1;
6
7 return n*Factorial(n-1);
8
9 }
10
11 }
你知道的,n的阶乘实际上就是n-1的阶乘乘以n,且n>0;
它可以表示成Factorial(n)=Factorial(n-1)*n;
这是方法的返回值,但我们需要一个条件,也就是出口(注意:递归一定要有出口)
如果n=0则返回1;
现在这个程式的逻辑应该很清楚了,这样我们就能够轻易的理解了.
2.(Fibonacci)斐波拉切数列:
Fibonacci数列是按以下顺序排列的数字:
1,1,2,3,5,8,13,21,34,55....
我们不难发现数列的排列规律是:后一个数加上前一个数,以此类推;
如果F0=0并且F1=1那么Fn=F(n-1)+F(n-2);
下面是计算Fabonacci数列的一种实现方法(没有使用递归):
1 public long Fibonacci(int n){
2
3 int a=1;
4
5 int b=1;
6
7 int n; // 声明一个变量用来定义数列的长度;
8
9 for(int i=2;i<n;i++){
10
11 b=a+b; // 得到b的值;
12
13 a=b-a; // 得到上一次a的值;
14
15 }
16
17 }
// 递归方法:
1 public long Fabinacci(int n){
2
3 if(n==0||n==1){ // 满足条件
4
5 return n;
6
7 }
8
9 return Fabinacci(i-2)+Fabinacci(i-2); // 返回值
10
11 }
我们通过排列发现,Fabonacci数列实际上就是后一个数加上前一个数的和
Fabonacci(n)=Fabonacci(n-2)+Fabonacci(n-1);
当数列元素从0开始排列时,满足判断条件得到返回值 n;
然后跳出进行下面语句,一直循环到满足n的条件,跳出出口得到返回值Fabonacci(n);
总结:方法实现体内再次调用方法本身的本质是多个方法的简写;
它既可以调用其他方法,又可以调用自身.
递归一定要有出口;
例:
1 public void Func1(ref int num){
2
3 if(num<3){
4
5 num++;
6
7 Func2(ref num);
8
9 }
10
11 }
12
13
14
15 public void Func2(ref int num){
16
17 if(num<3){
18
19 num++;
20
21 Func3(ref num);
22
23 }
24
25 }
26
27
28
29 public void Func3(ref int num){
30
31 if(num<3){
32
33 num++;
34
35 Func4(ref num);
36
37 }
38
39 }
40
41
......
那么我们可以将上述方法直接简写:
1 public void Func(ref int num){
2
3 if(num<3){
4
5 num++;
6
7 Func(ref num);
8
9 }
10
11 }