经常会看到一些人,问你,“来,写一个递归算法吧”。递归算法真的那么好吗?下面是经常看到的一些题目,还有,递归算法的优缺点!
常见题:
1、计算数组{1,1,2,3,5,8,13...}第30位的值
Process1
Static void Main(string[] args)
{
Console.WriteLine(Process1(30));
Console.ReadKey();
}
Public Static int Process1(int i)
{
if(i==0) return 0;
if(i==1) return 1;
else
return Process1(i-1)+Process1(i-2);
}
从此递归我们可以看出,递归就是从后面往前推获得数据,然后进行运算
但是如果第一题中的30改为40或者更大的数字,你有没有试过呢?
下面我们用Stopwatch来检测一下运行时间
递归-时间检测
static void Main(string[] args)
{
Stopwatch watch = new Stopwatch();
watch.Start();
Console.WriteLine(Process1(40));
Console.WriteLine(watch.Elapsed);
watch.Stop();
Console.Read();
}
public static int Process1(int i)
{
if (i == 1) return 1;
else if (i == 2) return 1;
else
{
return Process1(i - 1) + Process1(i - 2);
}
}
我们运行程序,卡一会,然后输出结果为:
运行了5秒,这才是当i=40的时候,那如果设置i为50,或更大,那要等的时候就更长了。
递归优点,简单明了,容易理解;缺点,就是效率低。
下面我们来优化一下,用如下的代码:
优化方法-时间监测
static void Main(string[] args)
{
Stopwatch watch = new Stopwatch();
watch.Start();
int[] num = new int[40];
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[39]);
watch.Stop();
Console.WriteLine(watch.Elapsed);
Console.ReadKey();
}
然后我们来看一些运行结果如何:
运行的时间,瞬间缩短了。。。。。。。。。
这种方法,将数据从前往后推,得出最终结果。
看来我们以后还要慎用递归算法。
2、计算1+2+3+4+...+100的值
Process2
static void Main(string[] args)
{
Console.WriteLine(Process2(100));
Console.ReadKey();
}
Public Static int Process2(int i)
{
if(i==0) return0;
else
return Process2(i-1)+i;
}
3、计算1-2+3-4+5-6+7...+49-50的值
这个算法该怎么写呢?!
欢迎回复,算法多多益善....
分享到:
相关推荐
c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘...
宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归
C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归
文件递归-XML递归-树图递归 面试中的常见递归算法:附带截图和详细代码
.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法
快速选择非递归与递归算法实现
递归和非递归方式计算Ackerman函数。非递归方法用堆栈实现。代码内部有详细的注释说明,比较适于学习。
包含多个经典的递归应用代码: 1.fibonacci.c 是斐波拉契数列递归解法 2.hanoi.c 是汉诺塔递归算法 3.permutation.c 是全排列递归算法 4.queen.c 是八皇后递归算法 5. reverse.c 是递归的测试代码 6.strlrn.c 是求...
ackman函数的递归和非递归,学习数据结构的素材,非递归是使用堆栈实现的。
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
二叉树递归与非递归遍历
递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树递归动态树...
c++实现的合并排序算法 用递归和非递归两种方式实现的
递归在计算学科中是一种非常重要的方法,计算理论中到处都有用递归进行表述的问题及求解方法。 在程序设计中,数据描述和算法表达也常用递归,通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题...
省市县递归函数
3.使用递归 先序遍历一棵二叉树 4.使用递归 中序遍历一棵二叉树 5.使用递归 后序遍历一棵二叉树 6.使用非递归 先序遍历一棵二叉树 7.使用非递归 中序遍历一棵二叉树 8.使用非递归 后序遍历一棵二叉树 PS:代码为C++...
二叉树递归非递归遍历(递归前中后,非递归前中后,层次遍历)
递归先序遍历二叉树: 递归中序遍历二叉树: 递归后序遍历二叉树: 非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单...
遍历递归的先中後序, 非递归的先中後序, 计算出深度 结点数 /* 运行结果: ------------------------ 请先序输入二叉树(如:ab三个空格表示a为根节点,b为左子树的二叉树) ab c 先序递归遍历二叉树: a b c 先序...
递归算法详解递归算法详解递归算法详解递归算法详解