1）1、1、2、3、5、8.......用递归算法求第30位数的值？
首先我们可以发现从第3位数起后一位数等于前两位数值之和，即：x=（x-1）+（x-2），x>2;
这里需要不断的相加，第一时刻就会想到循环处理，我们尝试用数组去装载这些数值，即：
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位数的值。
递归该如何处理呢？同样定义函数
fun(n)
{
return fun(n-1)+fun(n-2)//n为第几位数，第n位数返回值等于第n-1位数的值与第n-2位数的值之和
}
只有当n>2为这种情况，就可以做个判断
fun(n)
{
if(n==1 || n==2)
return 1;
else
return fun(n-1)+fun(n-2);
}
求fun(30);
网站看到别人的分析也不错：
【问题】 编写计算斐波那契（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时）。
写成递归函数有：
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项。
其他递归解题：
求1+2+3+4+5+....+n的值
Fun(n)=n+Fun(n-1)
n=1时为1
Fun(n)
{
if(n==1)
return 1;
else
return n+Fun(n-1);
}
有两个整数型数组，从小到大排列，编写一个算法将其合并到一个数组中，并从小到大排列
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];
}
}
首先碰到的是这样的一首题目：计算数组{1,1,2,3,5,8.......} 第30位值，不用递归，我写出了以下这样的代码：
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(); 
}
写出来，十分的累赘，于是改为归递算法来写，一目了然，十分明了。以下是代码：
static void Main(string[] args) { Console.WriteLine(Process1(30)); Console.ReadLine(); } public static int Process1(int i) { //计算数组{1,1,2,3,5,8.......} 第30位值 if (i == 0) return 0; if (i == 1) return 1; else return Process1(i - 1) + Process1(i - 2); }
做了一些练习：
1. 计算1+2+3+4+...+100的值
static void Main(string[] args) { Console.WriteLine(Process2(100)); Console.ReadLine(); } public static int Process2(int i) { //计算1+2+3+4+...+100的值 if (i == 0) return 0; return Process2(i - 1) + i; }
2. 计算1 -2 +3 +-4+ 5- 6 + 7 - 8 + 9的值
static void Main(string[] args) { Console.WriteLine(Process3(9) - Process3(8)); Console.ReadLine(); } public static int Process3(int i) { //计算1 -2 +3 +-4+ 5- 6 + 7 - 8 + 9的值 if (i == 0) return 1; if (i == 1) return 2; else return Process3(i - 2) + i; }
3.汉诺塔问题
static void Main(string[] args) { Hanoi(5, 'A', 'B', 'C'); Console.ReadLine(); } public static void Hanoi(int n ,char A, char B, char C) { //汉诺塔问题 //将n个盘子从A座借助B座，移到C座 if (n == 1) Move(A, C); else { Hanoi(n - 1, A, C, B); Move(A, C); Hanoi(n - 1, B, A, C); } } public static void Move(char startPlace, char endPlace) { Console.WriteLine("Move {0} To {1}",startPlace,endPlace); }
4.用递归法将一个整数n转换成字符串，例如，输入483,就输出字符串"483".n的位数不确定，可以是任意位数的整数。
static void Main(string[] args) { IntToString(483, ""); Console.ReadLine(); } public static void IntToString(int input,String output) { //用递归法将一个整数n转换成字符串，例如，输入483,就输出字符串"483".n的位数不确定，可以是任意位数的整数。 // String output = ""; output = input % 10+output; if (input / 10 != 0) { IntToString(input / 10,output); } else Console.WriteLine(output); }
------------------------------------------二分查找算法：http://blog.csdn.net/dinglang_2009/article/category/1435813
相关文章
