递归算法与优化后的算法对比
- - 博客园_首页前段时间看了《 【面试】——反应迟钝的递归》中的三个递归算法，斐波那契数列优化后的算法思路确实不错，但是后面2个数列用递归的话，个人感觉有点得不偿失. 能不用递归的话，尽量不用，因为有些算法完全可以用数学来解决. 因此，本文中将这三个数列的最终算法总结如下. 1、计算数组1,1,2,3,5,8,13...第30位的值.
递归算法与优化后的算法对比
标签：
递归
算法
优化
| 发表时间：2012-02-22 01:02 | 作者：JasenKin
出处：http://www.cnblogs.com/
前段时间看了《 【面试】——反应迟钝的递归》中的三个递归算法，斐波那契数列优化后的算法思路确实不错，但是后面2个数列用递归的话，个人感觉有点得不偿失。能不用递归的话，尽量不用，因为有些算法完全可以用数学来解决。因此，本文中将这三个数列的最终算法总结如下。
1、计算数组1,1,2,3,5,8,13...第30位的值
递归算法如下：
public static int CalculateFibonacciSequence(int index)
{
if (index <= 0)
{
return 0;
}
if (index == 1 || index == 2)
{
return 1;
}
return CalculateFibonacciSequence(index - 1) + CalculateFibonacciSequence(index - 2);
}
{
if (index <= 0)
{
return 0;
}
if (index == 1 || index == 2)
{
return 1;
}
return CalculateFibonacciSequence(index - 1) + CalculateFibonacciSequence(index - 2);
}
用递归算法来计算的话，有很多重复性的操作，采用数组相对来说，效率更高，最终算法如下：
public static int CalculateFibonacciSequence(int index)
{
if (index <= 0)
{
return 0;
}
if (index == 1 || index == 2)
{
return 1;
}
int[] fibonacciArray = new int[index];
fibonacciArray[0] = 1;
fibonacciArray[1] = 1;
for (int innerIndex = 2; innerIndex < fibonacciArray.Length; innerIndex++)
{
fibonacciArray[innerIndex] = fibonacciArray[innerIndex - 1] + fibonacciArray[innerIndex - 2];
}
return fibonacciArray[index - 1];
}
{
if (index <= 0)
{
return 0;
}
if (index == 1 || index == 2)
{
return 1;
}
int[] fibonacciArray = new int[index];
fibonacciArray[0] = 1;
fibonacciArray[1] = 1;
for (int innerIndex = 2; innerIndex < fibonacciArray.Length; innerIndex++)
{
fibonacciArray[innerIndex] = fibonacciArray[innerIndex - 1] + fibonacciArray[innerIndex - 2];
}
return fibonacciArray[index - 1];
}
对于斐波那契数列，通用公式为Fn=F(n-1)+F(n-2)（n>=2，n∈N*），直接循环计算一次就可以获得所需的值。
2、计算1+2+3+4+...+n的值
递归算法如下：
public static int CalculateNumberSequenceCount(int index)
{
if (index <= 0)
{
return 0;
}
return CalculateNumberSequenceCount(index - 1) + index;
}
{
if (index <= 0)
{
return 0;
}
return CalculateNumberSequenceCount(index - 1) + index;
}
当数字（index）很大时，用上面的递归算法肯定是有问题的，我们看下最终的算法，如下所示：
public static int CalculateNumberSequenceCount(int index)
{
if (index <= 0)
{
return 0;
}
return index * (index + 1) / 2;
}
{
if (index <= 0)
{
return 0;
}
return index * (index + 1) / 2;
}
对于1+2+3+4+...+n，完全是高中数学的等差数列求和的一个特例。1+2+3+4+......+n等于（首项+末项）*项数/2，所以结果为n(n+1)/2 。这个完全可以不用递归来进行计算，公式套用一下就解决了。
3、计算1-2+3-4+5-6+7+...+n的值
递归算法如下：
public static int CalculateNumberSequence(int index)
{
if (index <= 0)
{
return 0;
}
return index % 2 == 0 ? CalculateNumberSequence(index - 1) - index : CalculateNumberSequence(index - 1) + index;
}
{
if (index <= 0)
{
return 0;
}
return index % 2 == 0 ? CalculateNumberSequence(index - 1) - index : CalculateNumberSequence(index - 1) + index;
}
对于1-2+3-4+5-6+7+...+n，可以分为2种情况，分别为：
（1）当n是偶数时，1-2+3-4+5-6+7+...+n=(1-2)+(3-4)+(5-6)+……+[(n-1)-n]
=-1×（n/2）
=-n/2
（2）当n是奇数时，1-2+3-4+5-6+7+...+n=(1-2)+(3-4)+(5-6)+……+[(n-2)-(n-1)]+n
=-1×(n-1)/2 +n
=(n+1)/2
因此，最终的算法如下：
public static int CalculateCrossNumberSequence(int index)
{
if (index <= 0)
{
return 0;
}
return index % 2 == 0 ? -index / 2 : (index + 1) / 2;
}
{
if (index <= 0)
{
return 0;
}
return index % 2 == 0 ? -index / 2 : (index + 1) / 2;
}
能够用数学解决的问题，尽量不要用递归来进行计算。当然，很多情况还是需要用递归的。这里并不是说递归算法不好，只能说具体问题采用最优方式来解决才是最终的方案，希望对各位有所帮助。
相关 [递归 算法 优化] 推荐：
如何将递归转换为非递归 - coderkian
- - 博客园_首页递归函数具有很好的可读性和可维护性，但是大部分情况下程序效率不如非递归函数，所以在程序设计中一般喜欢先用递归解决问题，在保证方法正确的前提下再转换为非递归函数以提高效率. 函数调用时，需要在栈中分配新的帧，将返回地址，调用参数和局部变量入栈. 所以递归调用越深，占用的栈空间越多. 如果层数过深，肯定会导致栈溢出，这也是消除递归的必要性之一.
如何优化大规模推荐？下一代算法技术JTM来了
- - 机器之心阿里妹导读：搜索，推荐和广告是互联网内容提供商进行价值创造的核心业务，在阿里巴巴的电子商务交易平台上，搜索，推荐和广告业务同样具有举足轻重的意义和价值. 现在，阿里推荐技术又双叒优化了，新的推荐技术，新的体验，一起来看. 搜索、推荐和广告看似业务形态不同，其实技术组成却是非常相通的. 从推荐的视角看，搜索可以认为是一种带query相关性约束的推荐，而广告则是叠加了广告主营销意愿（价格）约束的推荐，所以推荐技术的创新对推动搜索、推荐和广告业务技术的整体发展具有基础性的作用.
PHP正则之递归匹配
- KnightE - 风雪之隅作者: Laruence(. 本文地址: http://www.laruence.com/2011/09/30/2179.html. 我记得早前有同事问, 正则是否能处理括号配对的正则匹配. 比如, 对于如下的待匹配的字符串:. 在以前, 这种情况, 正则无法处理, 最多只能处理固定层数的递归, 而无法处理无线递归的情况… 而在perl 5.6以后, 引入了一个新的特性: Recursive patterns, 使得这种需求可以被正确的处理..
Google向全球多数语言推广新算法“熊猫”优化搜索排名
- flycondor - 36氪Google最近开始推广代号为“熊猫”的搜索排名算法，将应用到不包括中文，日文和韩文在内的全球多数语言. 新算法的目的在于减少混迹于搜索结果中“内容农场”的数量. 根据市场研究机构Experian Hitwise的报告，“熊猫”在清除“内容农场“方面表现不错. 今年二月“熊猫”算法在美国率先推出后，最大的“内容农场”Demand Media旗下的eHow.com在两周内搜索结果锐减40%.
使用递归唯一性验证的方式生成主键
- - CSDN博客数据库推荐文章JadePool作为简化JDBC编程工具，提供 主键生成方法是必须的. 在JadePool中，ProcessVO用于事务型数据库的DML操作，Access用于非事务型数据库的DML操作，Access参照ProcessVO实现. 目前，JadePool只提供了单主键的键值生成方法，没有提供复合主键的生成方法.
SQLserver, Oracle 限制层数 递归查询和反向查询父记录
- - Oracle - 数据库 - ITeye博客以前使用Oracle，觉得它的递归查询很好用，就研究了一下SqlServer，发现它也支持在Sql里递归查询. SqlServer2008版本的Sql如下：. 比如一个表，有id和pId字段，id是主键，pid表示它的上级节点，表结构和数据：. --下面的Sql是查询出1结点的所有子结点. select * from my1 --结果包含1这条记录，如果不想包含，可以在最后加上:where id <> 1.
缓存算法
- lostsnow - 小彰没有人能说清哪种缓存算法由于其他的缓存算法. （以下的几种缓存算法，有的我也理解不好，如果感兴趣，你可以Google一下 ）. 大家好，我是 LFU，我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法，我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候，用了哪个缓存对象.
BFPRT算法
- zii - 小彰BFPRT算法的作者是5位真正的大牛（Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan），该算法入选了在StackExchange上进行的当今世界十大经典算法，而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度.
贪心算法
- Shan - 博客园-首页原创精华区顾名思义，贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择. 当然，希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解. 如单源最短路经问题，最小生成树问题等.