递归算法是什么？

作者：网络转载发布时间：[ 2013/1/10 9:50:23 ] 推荐标签：

　　一、基本概念

　　递归算法是一种直接或者间接调用自身函数或者方法的算法。Java递归算法是基于Java语言实现的递归算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。递归算法，其实说白了，是程序的自身调用。它表现在一段程序中往往会遇到调用自身的那样一种coding策略，这样我们可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁非常直观的代码形势，从而使我们的编码大大简化，然而递归的思维确实很我们的常规思维相逆的，我们通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。这样我们能看到我们会用很少的语句解决了非常大的问题，所以递归策略的主要体现是小的代码量解决了非常复杂的问题。

　　递归算法解决问题的特点：

　　1)递归是方法里调用自身。

　　2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

　　3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

　　4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

　　在做递归算法的时候，一定要把握住出口，也是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的，是一个条件，当满足了这个条件的时候我们不再递归了。

　　二、程序示例

　　①斐波纳契数列(Fibonacci Sequence)

　　问题描述：求解Fibonacci数列的第n个位置的值?(斐波纳契数列(Fibonacci Sequence)，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F1=1，F2=1，Fn=F(n-1)+F(n-2)(n>2，n∈N*))。

　　求解代码：

　　[java] view plaincopyprint?

　　public class Fibonacci {

　　/**

　　* time:2012.12.2

　　* author:王金宇

　　* description:用递归实现斐波那契数列，但是此方法是嫉妒危险的，适用于求解比较小的位置数值

　　public static void main(String[] args) {

　　Fibonacci fibonacci=new Fibonacci();

　　int result=fibonacci.fib(5);

　　System.out.println(result);

　　}