1）1、1、2、3、5、8.......用递归算法求第30位数的值？
首先我们能够发现从第3位数起后一位数等于前两位数值之和，即：x=（x-1）+（x-2），x>2;
这里须要不断的相加，第一时刻就会想到循环处理，我们尝试用数组去装载这些数值，即：
|
1
2
3
4
5
6
7
|
int[] a=new int[30]; a[0]=1; a[1]=1; for(int i=2;i<30;i++){ a[i]=a[i-1]+a[i-2];} |
求a[29]的值即为第30位数的值，递归该怎样处理呢？相同定义函数
|
1
2
3
4
|
fun(n){ return fun(n-1)+fun(n-2)//n为第几位数，第n位数返回值等于第n-1位数的值与第n-2位数的值之和} |
仅仅有当n>2为这样的情况，就能够做个推断
|
1
2
3
4
5
6
7
|
fun(n){ if(n==1 || n==2) return 1; else return fun(n-1)+fun(n-2);} |
求fun(30);
2）编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）斐波那契数列为：0、1、1、2、3、……，
即：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) （当n>1时）
写成递归函数有：
|
1
2
3
4
5
6
|
int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } |
递归算法的运行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。
比如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能马上得到结果1和0。在递推阶段，必需要有终止递归的
情况。比如在函数fib中，当n为1和0的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，比如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。
在编写递归函数时要注意，函数中的局部变量和參数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的參数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的參数和局部变量。
因为递归引起一系列的函数调用，而且可能会有一系列的反复计算，递归算法的运行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编敲代码。比如上例计算斐波那契数列的第n项的函数fib(n)应採用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。
3）求1+2+3+4+5+....+n的值
|
1
2
3
4
5
6
7
8
9
|
Fun(n)=n+Fun(n-1)n=1时为1Fun(n){ if(n==1) return 1; else return n+Fun(n-1);} |
4）有两个整数型数组，从小到大排列，编写一个算法将其合并到一个数组中，并从小到大排列
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
public void Fun() { int[] a = { 1, 3, 5, 7, 9, 10 }; int[] b = { 2, 4, 6, 8, 11, 12, 15 }; int[] c = new int[a.Length + b.Length]; ArrayList al=new ArrayList(); int i=0; int j=0; while (i <= a.Length - 1 && j <= b.Length - 1) { //循环比較把小的放到前面 if (a[i] < b[j]) { al.Add(a[i++]); } else { al.Add(b[j++]); } } //两个数组的长度不一样，必有个数组没比較完 while (i <= a.Length - 1)//加入a中剩下的 { al.Add(a[i++]); } while (j <= b.Length - 1)//加入b中剩下的 { al.Add(b[j++]); } for (int ii = 0; ii <= c.Length-1 ; ii++) { c[ii] = (int)al[ii]; } } |
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注服务器之家的更多内容！
原文链接：https://www.cnblogs.com/zhaoyl9/p/10304620.html
